떠도는 것을 좋아하는 진우는 어느 날 전설에만 존재하는 줄 알았던 근우조교의 마을에 도착하게 되었다. 이 마을은 특이한 점이 있었는데, 첫 째로 N행 N열의 0이상 3이하의 숫자가 새겨져 있는 정사각형이 붙어있는 형태로 이루어져 있으며, 또한 무조건 동쪽 혹은 남쪽 방향으로만 이동이 가능하다는 것이다. 진우는 아래 그림의 실선으로 그려진 동그라미가 놓여 있는 곳에 서있다. 진우는 점선의 동그라미가 놓여있는 위치에 정현이라는 노래를 잘 부르는 가수가 있다고 하기에 그곳까지 가려고 한다. 편의상 진우의 위치를 (1,1)라고 하고, 정현이가 있는 위치는 (N,N)라고 하자.

하지만 근우조교의 마을은 위에서 이야기한 특이한 점 외에도 또 특이한 점이 있다. 해당 위치에서 다른 곳으로 이동을 하려면 무조건 자신이 서있는 숫자의 칸만큼만 이동이 가능하다. 만약 진우가 위치한 사각형에 0이 있으면 더 이상 아무데도 갈 수 없게 된다. 아래 그림은 마을이 위의 그림처럼 이뤄져 진우가 이동 할 수 있는 모든 경우를 보여준다.

이동 방법이 유일하지 않다는 것을 알게 된 진우는 자신이 정현이에게 가려고 이동할 때 가능한 경우가 몇 가지인지 궁금해졌다. 진우의 궁금증을 해소해주자.

#1432 upload 62 done 14 how_to_reg 14

여행123 timer 1s memory 64MB

#1432

여행123 1s 64MB