하노이 탑 검증하기 1 timer 1s memory 128MB

하노이 문제는 기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때, 

아래의 규칙에 따라 1번 기둥에 있는 모든 원판을 3번 기둥으로 이동하는 문제이다.

규칙1) 한 번에 하나의 원판만 이동시킨다.

규칙2) 작은 원판위에 큰 원판을 놓을 수 없다.​

하노이 탑 완구를 가지고 위 문제를 풀던 수정이는 당신에게 ​현재 상태를 보여주며 ​이 상태가 올바른 상태인지 물어보았다.

올바른 상태란, ​위 규칙대로 ​최소 이동 횟수로 하노이 탑 문제를 해결하는 과정에서 나오는 상태를 말한다.

예를 들어​, 입력이 211이면, 가장 작은 원판은 2번 기둥에, 그다음 원판은 1번 기둥에, 가장 큰 원판도 1번 기둥에 있을 때, 

아래 그림처럼 올바르지 않은 상태다. (최소 이동 횟수대로 이동하면 나올 수 없는 상황이다)

현재 원판들의 위치 상태가 주어졌을 때 수정이의 하노이 탑이 올바른 상태인지 알려주자.