백준 11729 - 하노이 탑 이동 순서

🔐 백준 11729 - 하노이 탑 이동 순서

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

🔑 풀이

도저히 풀이가 생각나지 않아 다른 사람의 풀이를 참고하여 풀었다.

기본 풀이 방법은 다음과 같다.

• n개의 원판 중 n-1개의 원판을 목적지가 아닌 칸으로 옮긴다.

• 맨 밑의 n번째 원판을 목적지로 옮긴다.

• 나머지 n-1개의 원판을 목적지로 옮긴다.

위의 방법을 재귀적으로 반복하면 결과를 도출해 낼 수 있다.

원판 n개를 모두 옮기는 횟수를 T(n)이라 하고, 위의 방법을 식으로 나타내면,

1. 원판 n-1개를 중간 기둥으로 옮긴다. → 이동 횟수 : T(n-1)

2. 맨 밑의 원판을 목적지로 옮긴다. → 이동 횟수 : 1

3. 중간 기둥의 n-1개를 목적지로 옮긴다. → 이동 횟수 : T(n-1)

따라서, T(n) = 2T(n-1) + 1 이라는 재귀적 공식으로 나타낼 수 있다.

또한, base case T(1) = 1 이고,

T(2) = 3

T(3) = 7

T(4) = 15

⋯ 이므로, $ T(k) = 2^k - 1 $ 이라는 결과를 얻어낼 수 있다.

(1 « k) 는 쉬프트 연산자를 사용하여 쉽게 $ 2^k $ 를 얻어낼 수 있는 방법이다.

k를 3이라 하면, (1 « 3) 의 결과 $ 0001_2 → 1000_2 $ 가 되어 결과적으로 $ 2^3 = 8 $ 이 된다.

🧩 코드