[Baekjoon] 11729번: 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

---

 

문제 해결 과정

착안

첫 번째 장대에 쌓여있는 \(N\) 개의 원판을 최소 이동 횟수로 세 번째 장대로 옮기기 위해서는, \(N-1\) 개의 원판을 두 번째 장대로 옮긴 뒤 가장 아래의 원판을 세 번째 장대로 옮기고 다시 \(N-1\) 개의 원판을 세 번째 장대로 옮기는 과정을 수행하여야 한다(이 방법이 정말 최소 횟수로 이동하는 방법인지에 대한 의문이 들 수도 있는데, 이와 관련해서는 수학적 귀납법(mathematical induction)을 통해 증명할 수 있다).

 

따라서, 재귀함수의 형태로 원판의 이동을 구현하고자 하였고 이동 과정의 출력은 원판 1 개가 이동하는 경우에 현재 위치에서 목표 위치로 이동하는 과정을 출력하고자 하였다.

 

한편, \(N\) 개의 원판을 최소로 이동하기 위한 이동 횟수를 구할 때 재귀함수 내에서 이동 횟수를 1씩 증가하며 계산하여도 되지만 하노이의 탑(Tower of Hanoi) 문제는 수학적으로 유명한 문제라 이동 횟수를 구하는 방법이 널리 알려져있으므로 이를 이용하여 이동 횟수를 간단하게 구할 수 있다.

 

\(N\) 개의 원판을 다른 장대로 옮기기 위해 필요한 이동 횟수를 \(a_{N}\)이라고 하면 위에서 언급한 것과 같이

$$a_{N} = 2 a_{N-1} + 1 $$

이다. 위의 점화식의 양변에 1을 더하면 \(i = 1, 2, ..., N\) 일 때 \(a_{i}\)에 대한 식을 아래와 같이 쓸 수 있다.

$$a_{N} + 1 = 2(a_{N-1} + 1)$$

$$a_{N-1} + 1 = 2(a_{N-2} + 1)$$

$$\vdots$$

$$a_{3} + 1 = 2(a_{2} + 1)$$

$$a_{2} + 1 = 2(a_{1} + 1) = 4$$

위의 식들을 변변 곱하면 (\(\prod_{i = m}^{n}a_{i}\) 는 \(m\)번째 항부터 \(n\)번째 항까지 모두 곱하는 것을 의미하는 수열 곱셈 연산자)

$$(a_{N} + 1) \Bigg( \prod_{i = 2}^{N-1}(a_{i} + 1) \Bigg) = ( 2^{N-2} \times 4 ) \Bigg( \prod_{i = 2}^{N-1}(a_{i} + 1) \Bigg)$$

$$\therefore (a_{N} + 1) = 2^{N}   \Longrightarrow   a_{N} = 2^N - 1$$

 

구현

이와 같은 거듭제곱을 계산 과정에 포함하는 문제에서 지수가 일정 이상으로 커지면(밑이 몇이냐에 따라 다르지만) 사용하는 자료형의 표현 범위에 따른 정수 오버플로(integer overflow)를 신경써야하는데, 문제에서 주어지는 최대 원판 갯수는 \(N = 20\) 이므로 \(a_{20} = 1048575\) 이며 이는 기본 자료형으로 표현 가능하기 때문에 큰 문제 없이 프로그래밍 할 수 있었다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <cmath>

using namespace std;

void Hanoi(int N, int from, int dest, int temp)
{
	if (N > 1)
		Hanoi(N - 1, from, temp, dest);

	cout << from << " " << dest << "\n";

	if (N > 1)
		Hanoi(N - 1, temp, dest, from);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	cout << (size_t)pow(2, N) - 1 << "\n";
	Hanoi(N, 1, 3, 2);

	return 0;
}

 

실행 결과