Informatica Online Judge

  The Tower of Hanoi III [0607 / 025F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 361   Total Tried : 434


The Champion of this Problem (C++) : tlsdydaud1 - ms / 98byte
My Best Submission (C++) : N/A

[JKJeong]

Background

하노이 탑 게임에 대한 규칙은 잘 알고 있을 것이다.

하지만 이번 하노이3는 새로운 기둥을 하나 더 추가했다.

따라서 규칙은 기존의 하노이와 같지만 아래 그림과 같이 기둥이 4개인 하노이에 도전하는 것이다.





규칙은 다음과 같다.

1) 한 번에 하나의 원판만 옮길 수 있다.
2) 반드시 큰 원판 위에 작은 원판이 올라가야 한다.
3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다.

만약 원판이 2개 라면,

- 1번 원판을 A에서 B로 옮긴다.
- 2번 원판을 A에서 D로 옮긴다.
- 1번 원판을 B에서 D로 옮긴다.

따라서 총 3번을 옮기면 모두 옮길 수 있다.

여러분은 n개의 원판이 주어질 때 이 원판을 옮기는 횟수를 출력하는 프로그램을 작성하시오.

Input

첫 줄에 한 정수 n이 입력된다.
(단, 1 <= n <= 30 )

Output

4개의 기둥을 이용하여 옮기는 최소 횟수를 출력한다.

IO Example

입력
2

출력
3

힌트
이 문제에 대해서, n <= 30일 때 최적의 경로를 찾음이 계산적으로 검사된 그리디 알고리즘이 존재한다.
https://en.wikipedia.org/wiki/Tower_of_Hanoi#Frame.E2.80.93Stewart_algorithm

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]