[C++] 백준 11729번 : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

---

 문제 풀이

재귀에서 가장 대표적으로 뽑히는 문제이다.

가장 기본적인 개념은 다음과 같다.

기둥은 3개로 출발 지점, 도착 지점, 임시 지점으로 나눌 수 있다.

따라서 원반을 출발점에서 도착점으로 옮기려면 3단계만 거치면 된다.

 1. From -> Other

 2. From -> To

 3. Other -> To

이 부분을 재귀적으로 구현해주면 된다!

 느낀 점

분할-정복 알고리즘에 대해서 공부하다가 같이 공부했다. 대표적으로 구현되는 코드에 대해서는 이해하지 못했다. 

조금 더 공부를 해야할 것 같은 알고리즘이다!

 코드

#include <iostream>

using namespace std;

int n;

int pow(int n) {
	int result = 1;
	while (n--) result *= 2;
	return result - 1;
}
void hanoi(int n, int from, int to) {
	if (n == 0) return;
	int other = 6 - from - to;

	hanoi(n - 1, from, other);
	cout << from << " " << to << "\n";
	hanoi(n - 1, other, to);
}
    

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	cout << pow(n) << "\n";
	hanoi(n, 1, 3);
}