하노이 탑 문제를 들어 보았을 것이다.

3개의 막대기 중 하나에 n개의 원판이 꽂혀 있고, 이 원판들을 다른 막대기로 옮기는 문제이다.

이 문제를 풀 때의 이동 회수가 2ⁿ-1임은 잘 알려져 있다.

하노이 탑에서 n개의 원판이 있을 경우에 이 원판의 이동 경로를 모두 출력하는 프로그램을 만드는 것은 쉬운 일이다.

하지만 n이 커지면 출력 개수가 2ⁿ-1이기 때문에 출력하지 못한다. (일반적인 하노이 문제와 같이 막대는 항상 3개로 한다.)

당신이 할 일은, 원판이 n개 있을 때, 최소한의 횟수로 이동시키는 방법 중에서, k번째에 어떤 작업을 수행해야 하는지를 출력하는 것이다.

k번째만을 출력하면 된다. 물론 k는 1에서 2ⁿ-1까지의 정수이다. 제한시간은 2초이다.

하노이탑(k번째 이동) timer 2s memory 64MB

하노이탑(k번째 이동) 2s 64MB