[백준 11729] 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

n층 탑이 1에서 3으로 가기 위한 이동 횟수를 $F_n$이라고 하자

 

n층의 탑을 1에서 3으로 옮기는 순서는 다음과 같다.

 

 

n-1층의 탑을 1에서 2로 옮긴다

 

n번째 블럭을 1에서 3으로 옮긴다

 

2로 옮긴 n-1층의 탑을 2에서 3으로 옮긴다.

 

 

결국 아래와 같은 식이 성립한다.

 

$$F_n = 2*F_{n-1}+1$$

 

따라서 $F_n$은 $O(n)$안에 구할 수 있다.

 

---

 

위에 굵은 글씨로 되어있듯이 n층을 옮기는 작업은 n-1층을 옮기는 문제로 부분화할 수 있다.

 

따라서 n-1층을 옮기는 문제는 n-2층을 옮기는 문제로

 

n-2층을 옮기는 문제는 n-3층을 옮기는 문제로

 

계속 내려가다보면 1층을 옮기는 문제, 블럭 하나만 옮기면 되는 문제로 부분화할 수 있다.

 

이는 재귀함수를 통해 구현할 수 있다.

 

---

 

여기서 문제는 n-1층의 탑을 어디서(from) 어디로(to) 옮기는가이다.

 

from, to를 제외한 남는 공간 res라고 하자.

 

만약 n층을 탑을 옮긴다면

 

n-1층의 탑을 from에서 res로 옮긴다

 

n번째 블럭을 from에서 to로 옮긴다

 

res로 옮긴 n-1층의 탑을 res에서 to로 옮긴다.

 

결국 n-1층의 탑을 옮기는 문제에서는 n층 탑의 res가 to가 되고 to가 res가 된다.

 

다시 원래 위치로 옮기는 문제도 같은 방법으로 다뤄줄 수 있다.

 

---

 

코드를 읽고 설명을 읽는 것이 더 이해하기 쉬울 것이다.

 

#include <iostream>
#define n_ 200
using namespace std;

void rec(int t, int from, int to, int tmp) {
	if (t == 1) {
		printf("%d %d\n", from, to);
		return;
	}
	rec(t - 1, from, tmp, to);
	printf("%d %d\n", from, to);
	rec(t - 1, tmp, to, from);
}

int main(void) {
	int n;
	cin >> n;

	long long cnt = 1;
	for (int i = 1; i < n; i++) {
		cnt = cnt * 2 + 1;
	}
	cout << cnt << endl;
	rec(n, 1, 3, 2);
	return 0;
}