Baekjoon 18122. 색깔 하노이 탑 / Python

 

print((2**(int(input())+2)-5)%(10**9+7))

https://www.acmicpc.net/problem/18122

사실상 수학 문제이다.

하노이 탑 기본 원리

하노이 탑은 N개의 원판을 시작 기둥에서 목표 기둥으로 이동하는 문제입니다. 한 번에 하나의 원판만 이동할 수 있으며, 큰 원판이 작은 원판 위에 놓일 수 없습니다. 기본 하노이 탑 문제에서 N개의 원판을 이동하는 데 필요한 최소 이동 횟수는 다음과 같습니다:

T(N) = 2^N - 1

이 공식은 재귀적으로 문제를 해결하는 방식에서 유도된 것입니다.

두 개의 색깔이 있는 하노이 탑

문제에서는 원판이 두 색 (빨간색과 검은색) 이고, 각 크기별로 빨간색 원판과 검은색 원판이 번갈아 놓여 있습니다.

하노이 탑 게임의 목표는 모든 원판을 두 번째 기둥에서 세 번째 기둥으로 이동시키는 것입니다. 이동 규칙은 다음과 같습니다:

1. 한 번에 하나의 원판만 이동할 수 있다.
2. 큰 원판이 작은 원판 위에 놓일 수 없다.

두 색깔의 원판이 있는 경우의 이동 횟수

두 색깔의 원판이 있을 때, 각 원판의 크기별로 두 원판(빨간색과 검은색)이 번갈아 있는 상황을 고려해야 합니다.

이 문제는 빨간색과 검은색 원판을 구분하지 않고 단순히 원판의 개수에 따른 하노이 탑의 복잡성을 증가시키는 것이며, 이동 횟수를 계산할 때 색깔을 구분하는 것보다는 원판의 수에 따라 단순히 규칙을 확장하는 방식으로 접근할 수 있습니다.

수학적 유도

N개의 원판을 이동하는 최소 횟수는 다음과 같이 일반화됩니다:

• N개의 원판을 이동하는 하노이 탑의 최소 이동 횟수는 2^N - 1 입니다.
• 이 문제에서는 색깔이 두 개인 원판이기 때문에 이동 횟수가 단순히 원판의 수를 2배로 고려할 수 있습니다.

문제 해결을 위한 수식

이제, 문제를 해결하기 위해서 필요한 최소 이동 횟수는 다음과 같은 수식으로 구할 수 있습니다:

(2(N+2)−5)mod  (109+7)(2^{(N+2)} - 5) \mod (10^9 + 7)(2(N+2)−5)mod(109+7)

이 수식은 원판의 개수가 N일 때 하노이 탑의 이동 횟수를 계산하는 일반 수식을 기반으로 확장된 것입니다.

수학적 설명

1. 기본 이동 횟수:
2. T(N)은 2N−1입니다.
3. 두 색깔의 원판과 하노이 문제:
   • N개의 원판이 있을 때, 모든 원판을 올바르게 배치하려면 기본 문제보다 더 많은 이동이 필요합니다.
   • 기본 하노이 타워의 이동 횟수는 2^N−1이며, 이를 두 색깔의 원판으로 고려하면 2^{(N+2)} - 1 - (2^2 - 1)으로 계산할 수 있습니다.
   • 구체적인 식으로 변형된 문제의 이동 횟수를 구하기 위해 (2^{(N+2)} - 5) \mod (10^9 + 7) 를 사용합니다.
4. 문제는 빨간색과 검은색 원판을 모두 고려한 하노이 탑 문제의 변형입니다. 이 경우 이동 횟수는 기본 하노이 타워 문제의 이동 횟수에 기반을 두고 확장될 수 있습니다.

결론

따라서, N개의 원판을 사용하여 두 색깔이 있는 하노이 탑 문제를 해결하는 데 필요한 최소 이동 횟수는 다음과 같이 수학적으로 설명할 수 있습니다:

최소 이동 횟수 = (2^{(N+2)} - 5) \mod (10^9 + 7)

이 식의 유도는 기본 하노이 탑 문제에서 출발하여 색깔이 두 개인 경우로 확장된 문제의 해를 구하는 방식으로 접근할 수 있습니다.