동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그는 자신이 원래 살던 곳으로 돌아가고 싶었지만 너무 멀어서 갈 수 없었다. 그래서 그는 자신이 살던 곳의 전통방식으로 지어진 탑을 간절히 생각하며 슬픔을 달래기로 했다. 그 탑의 이름은 원숭이 타워!!
원숭이 타워는 원숭이들이 만든 것이라고는 하지만 원숭이들의 창의력이 부족하여 실제로는 하노이지방의 하노이타워를 응용하여 만든 탑이다. 이제 그 탑을 살펴보자.
위의 그림에 잘 나타나있다. 원숭이 타워가 하노이타워와 다른 점은 기둥을 네 개를 쓴다는 점이다. 이 탑의 목적은 하노이타워와 마찬가지로 디스크들을 1번 기둥에서 4번 기둥으로 모두 옮기는 것이다. 물론, 하노이타워의 규칙을 똑같이 적용해서 옮겨야 한다.
하노이타워의 규칙을 모르는 자들을 위해 하노이타워의 규칙을 설명하겠다.
작은 디스크는 항상 큰 디스크의 위에 놓여야 한다. 한 번에 딱 하나의 디스크를 다른 기둥으로 옮길 수 있다. 이제 원숭이는 머릿속으로 원숭이 타워를 생각하려 하는데 두뇌가 딸려서 잘 계산이 되지 않아 여러분에게 도움을 요청하였다. 처음에 1번기둥에 N개의 크기가 서로 다른 디스크가 쌓여있을 때, N개의 디스크를 모두 4번기둥으로 옮기는 최소회수를 구하는 프로그램을 작성하시오.
문제에서 명시된 것처럼, 이 Frame-Stewart conjecture 를 가지고 푸는 게 정신건강에 좋다.
r개 기둥의 n개 원판을 다른 기둥으로 옮기는 최적해를 T(n, r)이라고 두자. 그렇다면, 임의의 k에 대해 (상위 k개를 다른 원판으로 옮김) -> (하위 n-k개의 원판을 r-1개의 원판을 사용하여 다른 원판으로 옮김) -> (상위 k개의 원판을 바로 그 원판으로 다시 옮김)의 순서로 옮길 수 있으므로, 2*T(k, r) + T(n - k, r-1)의 재귀적인 식으로 나타낼 수 있다.
또한 본 문제의 r = 4이며, r = 3일 때는 T(n, 3) = 2^n - 1을 이용할 수 있다. 즉 우리는 T(n, 4) = 2*T(k, 4) + 2^(n-k) - 1이라는 수식에 대하여 최적의 k를 찾아야 하며, 위 링크에는 r = 4일때의 그 해인 k = n + 1 + round(sqrt(2*n+1))가 존재한다. 즉 재귀적으로 이 수식을 구현하면 된다.
...혹은, 이 최적화된 k를 dp로 일일히 풀어가며 푸는 방식이 있다. 어쨌든 k번 안에 T(k, 4)의 최적해를 찾을 수 있으므로. 위의 최적해 공식을 바로 이용하지 않고 DP를 토대로 풀이하면 되겠다.
...혹은, 좀 더 어려운(그리고 위 배경 지식이 없는 대부분의 사람들의 풀이법으로 생각되는) 군수열을 이용한 방법이 있다. r = 4일때의 최적해는 1 + 2 + 2 + 4 + 4 + 4 + .... = sum((k-1) * 2^k) 꼴로 나타나게 되므로, 최적해에 맞는 경우의 수를 따져 가며 구현해 볼 수도 있겠다.
풀이 코드
import sys
sys.setrecursionlimit(10**6)
N = int(input())
MOD = 9901
def roundup(num) :
return int(num) + 1 if (num - int(num)) >= 0.5 else int(num)
def hanoi(num) :
if num == 1 :
return 1
K = num + 1 - roundup((2*num + 1) ** 0.5)
return (2*hanoi(K) + 2 ** (num - K) - 1) % MOD
print(hanoi(N))
