원숭이 타워
시간 제한2초메모리 제한128 MB
네 개의 기둥이 있는 하노이의 탑에서 원판이 최대 백만 개일 때 최소 이동 횟수를 프레임-스튜어트 점화식으로 구하고 9901로 나눈 나머지를 출력합니다.
문제
원숭이 타워는 하노이 탑과 같은 규칙을 따르지만, 기둥이 4개인 탑이다.
처음에는 크기가 모두 다른 디스크 N개가 1번 기둥에 쌓여 있다. 목표는 모든 디스크를 4번 기둥으로 옮기는 것이다.
디스크를 옮길 때는 다음 규칙을 지켜야 한다.
- 큰 디스크를 작은 디스크 위에 올릴 수 없다.
- 한 번에는 디스크 하나만 다른 기둥으로 옮길 수 있다.
처음 상태에서 N개의 디스크를 모두 4번 기둥으로 옮기는 데 필요한 최소 이동 횟수를 구하시오.
입력
첫째 줄에 디스크의 개수 N이 주어진다. N은 1,000,000 이하의 자연수이다.
출력
첫째 줄에 N개의 디스크를 옮기는 데 필요한 최소 이동 횟수를 9901로 나눈 나머지를 출력한다.
힌트
이 문제는 네 기둥 하노이 탑의 최적 이동 횟수에 대한 Frame-Stewart 추측을 이용해 풀 수 있다.