하노이 탑 이동 순서 (feat. 백준, 11729번)

하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11729
#include <iostream>
using namespace std;
void solution(int num, int from, int by, int to) {
	if (num == 1) {
		cout << from << " " << to << "\n";
	}
	else {
		solution(num - 1, from, to, by);
		cout << from << " " << to << "\n";
		solution(num - 1, by, from, to);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, dp[21];
	dp[1] = 1, dp[2] = 3;
	cin >> N;
	for (register int i = 3; i <= N; ++i)
		dp[i] = (dp[i - 1] << 1) + 1;
	cout << dp[N] << "\n";
	solution(N, 1, 2, 3);
	return 0;
}
// *&)*@*

1. 3개인 경우, 2개를 2번에 옮기고 3번째를 3번에 옮긴다고 했을때, 결국 한개를 어떻게 옮길 것인가에 귀속됩니다.
2. 즉, 1에서 2를 거쳐 3으로 가는 것이므로 이를 재귀함수로 풀이하면 됩니다.