먼저 가장 떠올리기 쉬운 방법은 O(W+H)N)일텐데요...

극단적으로 1*1인 곳에서 N이 아무리커도 N의 홀짝성만으로 (1,2)에 위치할 지, (2,1)에 위치할 지 알 수 있겠죠?

이 아이디어를 가지고 동적 계획법을 수행합니다.

d(i, j, status) : 총 n번 지나갈 때 status방향(0이면 오른쪽, 1이면 아래쪽)으로 (i, j)를 지나간 횟수라고 정의합니다. 예를 들어 d(1,1,0)과 d(1,1,1)은 대략 n/2의 값을 가지겠죠(대략이라고 함은 홀짝성에 의해 1이 가감될 수 있으므로...) 그러면 d(i-1, j)와 d(i, j-1)만을 가지고 d(i, j)를 채울 수 있고 이를 이용하여 (i, j)에서 가야할 방향을 결정할 수 있습니다. 전체적인 시간복잡도는 O(WH)입니다.

감사합니다 ㅎㅎ 풀었어요