[BOJ / C++] 하노이 탑 이동 순서 (재귀)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

void hanoi(int st, int ed, int n) {
	if (n == 0) return;

	hanoi(st, 6-(st+ed), n-1);
	cout << st << ' ' << ed << '\n';
	hanoi(6-(st+ed), ed, n-1);
}

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

	int n;
	cin >> n;

	cout << (1<<n)-1 << '\n';
	hanoi(1, 3, n);
}

 

 

2. 분석

n개의 하노이탑을 st에서 ed로 옮길 때 n-1개의 하노이탑을 임시 탑(6-(st+ed))에 옮긴다는 것이 중요하다. 이후 n번째 블록을 st -> ed로 옮기고, 입시 탑에 있던 n-1개의 블록들을 ed로 옮겨주면 된다.

 

 

3. 시간복잡도

hanoi(n)에서 hanoi(n-1)을 두번씩 재귀호출하고 있다. 따라서 총 2^n - 1 번 함수 호출이 일어나게 된다. 따라서 시간복잡도는 O(2^n)이다.