BOJ 18122 : 색깔 하노이 탑

문제 링크

 

그림을 그리면서 관찰을 해보자.

먼저 n번째 원판들이 1->3으로 갈 때 옮기는 횟수는 n=1일 경우 3, n>1일 경우 2^(n+1)임을 알 수 있다. 

 

그렇다면 이를 n번째 원판들까지 있다고 할 때 옮기는 총 횟수를 식으로 나타내보자.

 

2^(n+1)+2^n+2^(n-1).....+2^3+3 

= 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0-4

= 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0+1-5

= 2^(n+2)-5

가 된다.

이제 이걸 계산해주면 되는데, 아주 큰 수를 계산한 나머지를 요구한다.

큰 수 계산, 거듭제곱 계산에는 Python이 더 유리하므로 파이썬으로 풀었다.

C++로 한다면, n의 최대가 10^6이므로 그냥 O(n)으로 곱하고 나머지 구해서 하면 된다.

코드