문제
전설의 하노이 탑 문제는 기둥이 3개이다.
기둥이 3개인 경우 N개 원판의 최소 이동 횟수는 2N - 1 인 것은 잘 알려진 사실이다.
기둥이 4개인 경우 원판의 최소 이동 횟수는 어떻게 될까?
기둥 번호는 차례로 A, B, C, D이고 N개의 원판을 A번 기둥에서 D번 기둥으로 옮겨야 한다.
규칙은 다음과 같이 기둥이 3개인 경우와 같다.
조건 1) 한 번에 하나의 원판만 옮길 수 있다.
조건 2) 반드시 큰 원판 위에 작은 원판이 있어야 한다.
조건 3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다.
입력
첫 행에 테스트 케이스의 수 T가 입력된다. ( 1 <= T <= 100)
두 번째 행부터 T개의 행에 원판의 수 N이 입력된다. (1 <= N <= 1,500)
출력
각 케이스에 대하여 A번 기둥에 쌓인 N개의 원판을 D번 기둥으로 옮기는 최소 횟수를 출력한다.
출력 결과의 범위는 unsigned long long 범위이다.
예제 #1
4
15
9
35
5
129
41
1665
13
예제 #2
3
7
27
124
25
705
589825
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.