하노이9(삼각하노이S) timer 1s memory 256MB

A, B, C 세개의 기둥이 있을 때, A번 기둥과 B번 기둥에 각각 N개의 원판이 아래 그림과 같이 주어진다.

기본 하노이 규칙에 3번 규칙을 추가하여 원판을 옮기는 문제를 생각해보자.

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있을 수 없다.

3. 같은 크기의 원판이 두 개 씩이며 같은 원판끼리는 서로 올려놓을 수 있다.

최종적으로 아래와 같은 결과를 얻고자 한다.

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