하노이 11 (사각 하노이 (Small)) timer 1s memory 256MB

다음과 같은 하노이 문제를 생각해 보자.

기둥이 4개, 원판이 2N개 주어진다.

1번 기둥에 N개, 2번 기둥에 N개 주어지며 두 기둥의 원판은 그림과 같이 같은 구성이다.

원판을 움직이는 규칙은 기둥이 비어 있거나 자신보다 크거나 같은 원반위로 이동할  수 있다.

1번 기둥과 2번 기둥에 있는 2N개의 원판을 3번 또는 4번기둥 하나에 모두 모으면 된다.​

아래 그림은 원판의 수 N이 2인 예이다.

1번 기둥과 2번 기둥에 있는 2N개의 원판을 3번 또는 4번기둥 하나에 모두 모을 때,

최소 이동수를 구하는 프로그램을 작성하시오.

 ​ ​