[platinum3] [해설안봄,분류안봄] 5573 산책

굉장히 특이하고 재미있는 문제였다. 마치 격자 한칸 한칸이 시계의 톱니바퀴 처럼 맞물려  주기성을 가지면서 돌아가 다음결과를 만들어내는 느낌이 들었다.

처음엔 dp 말고 그냥 N번째일 때 특정격자에서의 방향을 예측 가능할 거라고 생각해서 접근했지만 방법이 없었고,. 한참 고민하다가 아이디어가 떠올려 풀 수 있었다 ㅜㅜ

 

처음에 생각했떤 방법은 

다음과 같이 전부 아래로 써있는 판이 있으면, 밑으론 내려갈 수록 그 격자점을 밟는 횟수가 2배씩 늘어나므로, 주기성은  2 ^(시작점부터의 최단거리) 를 가질 것이다. 문제는 처음 시작할 때   (주기성 ) * K + a   에서 a는 상수이고 초기에 몇번째에 밟는 지에 따라 정해질텐데 이걸 구하는 것이다. 그런데 문제는 (2,2) 일때를 구하려면 (1,2) 일때와 (2,1)때의 주기성과 a 를 모두 고려해야 하고, 격자점이 최대 100만개인 상황에서 이건 불가능하다는 건 자명하다.

 

그래서 계속 아이디어를 생각하던중... 밥먹으며 생각하다가 밟는 횟수에 초점을 맞추면 되지 않을 까 번뜩 떠오르게 되었다. 짝수번,홀수번 밟느냐에 따라 오른쪽, 아래쪽이 결정될 테니까 말이다.

 

그럼 (i, j) 에서 (i - 1,j)격자를 밟는 횟수 와 초기상태(오른쪽인지 아래쪽인지) ,  (i,j - 1)에서의 밟는횟수와 초기상태를 안다면 (i,j)에서 오인지 아인지 알 수 있을 것이다.

 

 

(1,2)에서는 (위쪽) 초기상태가 아래쪽이므로, 처음밟자마자  (2,2)를 밟게 되므로 (2,2) 에서 (N + 1) / 2번 밟게 된다.

반면 (2,1)  (왼쪽) 에서는 처음밟았을 때 (2,2)로 안오고 2번째 부터 오게 되므로 (2,2)는 (M / 2)번 밟게 된다.

 

여기까지 알았으면 dp로 쉽게 구현 가능하다.

참 재밌고 퀄리티 높은 문제였다.