스핑크스의 수수께끼 timer 1s memory - MB

창환이가 모험 도중 스핑크스를 만났다.

“여기를 통과하려면 내가 내는 문제를 맞혀야 한다. 만약 그러지 못한다면 넌 나에게 잡아먹히게 될 것이다. 아침에는 네 다리로 그리고 저녁에는 세 다리로 걸으며 네 다리로 걸을 때가 더 연약한 존재는 무엇인가?”

“그거야 당연히 인간이지. 그 정도야 공부를 하고 왔다고.”

“하하하, 제법이군, 사실 지금 낸 문제는 연습문제이고, 진짜 문제는 이거다! 이 동굴은 가로와 세로가 각각 n개의 방으로 되어 있다. 너는 가장 북서쪽에 있는 방에서 시작해서 남동쪽에 있는 방까지 가야 한다. 단, 다음과 같은 규칙을 따라야 한다. 규칙을 어기는 순간 동굴은 무너질 것이다.”

스핑크스가 설명한 규칙은 다음과 같다.

(1) 각 방의 바닥에는 0이상 9이하의 정수 하나가 적혀 있다. (2) 이동방향은 동쪽 또는 남쪽으로만 가능하다. (3) 방에서 이동할 때, 바닥에 적혀 있는 숫자만큼 이동해야 한다. 예를 들어, 바닥에 3이 적혀 있으면 동쪽으로 세 번 또는 남쪽으로 세 번째의 방으로 가야 한다. 도중에 방향을 바꿀 수는 없다. (4) 바닥에 0이 적혀 있는 방에 도착하게 되면 더 이상 진행할 수 없다.

창환이는 스핑크스가 말한 방으로 들어갔고, 규칙을 지키면서 남동쪽 방까지 이동할 수 있는 경우의 수가 몇 가지나 될 지 궁금해졌다.

왼쪽의 그림은 바닥에 적혀 있는 숫자들을 나타내며, 나머지 세 개의 그림은 남동쪽으로 가는 가능한 경로 세 가지를 보여주고 있다(그림의 위쪽이 북쪽이며, 왼쪽이 서쪽이다).