세 기둥과 한 기둥 하노이 timer 1s memory 1024MB

3+1 하노이 탑 게임은 가로 방향으로 일렬로 놓인 4개의 기둥과 크기가 서로 다른 N개의 원판을 이용한 게임이다. 편의상 왼쪽에 있는 기둥부터 차례대로 A, B, C, D라고 하자.

처음에는 기둥 A에 크기가 가장 큰 원판이 아래에 오도록 모든 원판이 크기 순서대로 쌓여 있다. 이 게임의 목표는 아래 규칙을 지키면서 모든 원판을 기둥 D로 옮기는 것이다.

• 한 번에 한 개의 원판만 옮길 수 있다.

• 어떤 기둥의 맨 위에 있는 원판만 옮길 수 있다.

• 작은 원판 위에 큰 원판을 놓을 수 없다.

• 기둥 D에 있는 원판을 다른 기둥으로 옮길 수 없다.

• 기둥 A, B, C에 있는 원판은 위 조건을 어기지 않는 한 자유롭게 옮길 수 있다.

기둥 A에 있는 N개의 원판을 모두 기둥 D으로 옮기기 위해 필요한 최소 이동 횟수를 구하고, 그러한 이동 방법을 아무거나 하나 출력하시오.