E D R , A S I H C RSS

The Priest Mathematician

원문보기
----
인기도:C(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:2(1~4)

About ThePriestMathematician

"하노이의 탑(Tower of Hanoi)" 퍼즐에 관한 고대 신화는 이미 잘 알려져 있다. 최근 밝혀진 전설에 의하면, 브라흐마나 수도사들이 64개의 원반을 한 쪽 침에서 다른 쪽 침으로 옮기는 데 얼마나 오래 걸리는지를 알아내고 나서는 더 빠르게 옮기는 방법을 찾아내자는 결론을 내렸다. 다음 그림은 침이 네 개인 하노이의 탑이다.
http://online-judge.uva.es/p/v102/p10254b.jpg
사원에 있는 수도사 중 한 명이 동료 수도사에게 침을 하나만 추가하면 1초에 원반을 하나씩 옮긴다고 할 때 한 나절이면 모든 원반을 옮길 수 있을 것이라고 알려주었다. 그가 제안한 방법은 다음과 같다.
{{|
1. 맨 위에 있는 원반(맨 위에 있는 k개의 원반)을 다른 침으로 옮긴다.
2. 침이 세 개 있는 경우에 쓰는 방법을 그대로 적용해서 나머지 n-k개의 원반(전체 원반의 개수를 n개라고 가정)을 목표 지점으로 옮긴다.
3. 마지막으로 네 개의 침을 이용해서 맨 위에 있던 k개의 원반을 최종 목적지로 옮긴다.
|}}
이동 횟수를 최소화할 수 있는 k값을 계산한 다음 18,433번만 옮기면 된다는 결론을 내렸다. 따라서 침이 세 개만 있을 때는 5천억년이 걸릴 일을 침 하나만 추가하면 5시간 7분 13초만에 할 수 있다는 것을 알아냈다.

그 영리한 수도사가 제안한 네 개의 침을 사용하는 방법으로 원반을 옮기는 횟수를 계산하자. 원반은 한 번에 하나씩만 옮길 수 있으며 큰 원반을 작은 원반 위에 놓을 수는 없다. 이동 횟수를 구하려면 먼저 원반 이동 횟수를 최소화시킬 수 있는 k값을 구해야 한다.

Input

입력 파일은 여러 줄로 구성된다. 각 줄에는 0 이상 10,000 이하의 정수 N이 들어있으며, 이 값은 옮겨야 할 원반의 개수를 나타낸다. 파일 끝 문자가 들어오면 입력이 종료된다.

Output

입력된 각 줄에 대해 N개의 원반을 최종 위치로 옮기는 데 필요한 이동 횟수를 출력한다.

Sample Input

{{| 1
2
28
64 |}}

Sample Output

{{| 1
3
769
18433 |}}

풀이

작성자 사용언어 개발시간 코드
김상섭 C++ . ThePriestMathematician/김상섭
문보창 C++ 1차(실패), 2차(5시간) ThePriestMathematician/문보창
하기웅 C++ 2시간 30분 ThePriestMathematician/하기웅
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0926 sec