Informatica Online Judge

  Hanoi 4 (Large) [0722 / 02D2]

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


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

[29th 권태호]

Background

정호는 Stein***을 보다가 심심하여 하노이 탑 게임을 시작하였고, 하노이 탑 게임을 하다가 할 짓없이 기둥을 하나 더해서 기둥이 4개인 하노이에 도전하였다.




규칙은 다음과 같다. 

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

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

따라서 총 3번을 옮기면 모두 옮길 수 있다. 여러분은 n개의 원판이 주어질 때 이 원판을 옮기는 횟수를 출력하는 프로그램을 작성하시오.

Input

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

Output

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

IO Example

입력
2

출력
3

*출제 : 29th 권태호

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