[백준 / BOJ] 11729번: 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

 

---

코드

---

#include <iostream>
using namespace std;

void hanoi(int start, int by, int end, int num)
{
	//num이 1이라면 원판을 start에서 end로 이동시킴
	if (num == 1) {
		cout << start << ' ' << end << '\n';
	}
	else {
		//n-1개의 원판을 start에서 시작해 end를 거쳐 by로 이동시킴
		hanoi(start, end, by, num - 1);
		//n번째 원판을 start에서 end로 이동시킴
		cout << start << ' ' << end << '\n';
		//n-1개의 원판을 by에서 start를 거쳐 end로 이동시킴 
		hanoi(by, start, end, num - 1);
	}
}

int main() {
	int n;
	cin >> n;
	cout << (1 << n) - 1 << "\n";
	hanoi(1, 2, 3, n);
	return 0;
}

 

 

 

---

 

 

분할정복 유형으로, 재귀함수를 사용하여 풀 수 있는 문제이다.

분할정복 문제는 문제를 작은 문제로 나누는 방법을 찾아내는 과정이 제일 중요한것 같다.

하노이탑에서 n개의 원판을 옮기는 과정에서 시작 장대를 start, 최종적으로 옮겨야 하는 장대를 end, 옮기는 과정에서 거쳐갈 수 있는 장대를 by라고 할 때, 다음 과정으로 쪼개어 생각할 수 있다.

 

1. start 장대에 있는 위에서부터 n-1개의 원판을, start장대에서 end 장대를 거쳐 by 장대로 옮긴다.
2. start 장대에서 가장 밑에 있는 원판을 end 장대로 옮긴다.
3. by 장대에 있는 n-1개의 원판을 start 장대를 거쳐 end 장대로 옮긴다.

위 과정대로 재귀호출을 하다가 n=1이 될 때에는 단순히 start 장대에서 end 장대로 옮겨주기만 하면 된다.

 

* 하노이탑 이동 횟수 점화식

위 아이디어에 따라서, n개의 원판을 옮길 때의 이동 횟수 점화식을 구하면 다음과 같다.

$$ a_1 = 1 $$

$$ a_2 = 2a_1 + 1 $$

$$ a_3 = 2a_2 + 1 $$

$$ \vdots $$

위 과정을 토대로 일반항을 구하면 아래와 같다.

$$ a_n = 2a_{n-1} + 1 $$

식을 풀기 위해 아래 과정을 따라 변형한다.

$$ a_n = 2a_{n-1} + 1 $$

$$ a_n + 1 = 2a_{n-1} + 2 $$

$$ a_n + 1 = 2(a_{n-1} + 1) $$

공비 2, 첫째항 2인 등비수열이므로

$$ a_n + 1 = 2*2^{n-1} $$

$$ a_n + 1 = 2^{n} $$

$$ a_n = 2^{n} - 1 $$

 

따라서 n개의 원판에 대한 하노이탑 이동 횟수는 2^n - 1 이다.