/* 아하 저렇게 옆뒤 아래로 움직이는 행렬에 대한 문제가 나오는구나, 오케이요. 어떻게 처리하는지 천천히 살펴보도록 하겠습니다. 이 배열은 존재한다고 가정하고 몇번째에 무엇이 존재하는지 알면 됩니다. 그럼 예를 들어보도록 하겠습니다. 아니면 움직임을 가정하고 풀어보도록 하겠습니다. 저것을 저렇게 보지 말고 짝수열 홀수열 이렇게 보면 됩니다. 먼저 만들어 있는 행렬이라고 가정을 하고, 짝수열, 홀수 열 이렇게 보면 됩니다. 그리고 그안에서 규칙을 찾아보도록 하겠습니다. 예를 들어서 먼저 어디 행렬에 속하는지 먼저 찾아보면 14번쨰는 1+2+3+4+5+6+...+n 상황에서 먼저 어디에 속하는지 찾습니다. 그래서 14는 14-1 = 13 13 - 2 = 11 11-3 = 8 8-4 = 4 4>5 ? 노 이기때문에 5번째에 속하게 됩니다. 5번째에서도 5번쨰는 홀수번쨰이므로 아래에서 부터 시작하게 되는데, 4가 남았으므로 4번 이동하게 됩니다. 보면, 오케이, 위, 아래로 3번씩 이동하면 됩니다. 4-1=3 을 오른쪽 3번 위로 3번 이동하면 됩니다. 그럼 최종적으로 2행 4열이므로 답은 2/4 가 나오게 됩니다. 오케이요. 그럼 홀수인지, 짝수인지 먼저 나누고 시작하면 되겠습니다. 시작하도록 합니다. 이렇게 규칙을 찾으니 하나씩 풀려나가고 있습니다요. */ #include <iostream> using namespace std; int N; int cnt = 1; int row; int col; int res; void problemIn() { cin >> N; } /* 예를 들어서 8 이라고 가정을 하면 cnt 는 4이고, 2/3 이 나와야 합니다. 그러므로 */ void solve() { for (int i = 1; N > i; i++) { N = N - i; cnt++; } if (cnt % 2 == 1) { row = cnt; col = 1; for (int i = 1; i < N; i++) { row--; col++; } } else { row = 1; col = cnt; for (int i = 1; i < N; i++) { row++; col--; } }
cout << row << "/" << col << endl; } int main(void) { problemIn(); solve(); return 0; } |
행렬이 지그재그로 움직이는 것인데, 이것도 규칙있게 움직이므로 이것도 움직임을 표현할 수 있다. 이와 비슷한 문제를 본적이 있으므로, 이 규칙에 대해서도 풀이가 가능하다. 오케이요. 조금씩 손에 잡히고 있습니다. 이것 다음으로, 디피 문제와 완전탐색 문제까지 모두 풀어보도록 하겠습니다. 모든 유형을 쉽게 파악하도록 하겠습니다. 하루에 한문제 하더라도 80 문제 밖에 보지 못하므로, 지금 .... 80 에서 주말 빼면 50일이네... 헐헐.. 미쳤네... 50문제... 라니!!! 빠르게 1주만에 디피와 완전탐색까지 모두 돌파하도록 하겠습니다. |