[백준(BOJ) 11729번] 하노이 탑 이동 순서 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

풀이

 재귀를 이용해서 해결할 수 있는 문제이다. 재귀를 공부할 때 귀납적 사고를 통해서 해결하라는 말이 있다. n-1개의 원판을 2번 으로 모두 옮긴 후, n번 원판을 3번으로 옮기고, 2번으로 옮겼던 n-1개의 원판을 3번으로 옮기면 된다.

 

소스 코드

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

void func(int a, int b, int n) {
	if (n == 1) {
		cout << a << ' ' << b << '\n';
		return;
	}
	
	func(a, 6 - a - b, n - 1); // n - 1개 원판을 기둥 1에서 기둥 2로 옮기자.
	cout << a << ' ' << b << '\n'; // n번 원판을 기둥 1에서 기둥 3으로 옮기자.
	func(6 - a - b, b, n - 1); // n -1개 원판을 기둥 2에서 기둥 3으로 옮기자.
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	cout << (1 << n) - 1 << '\n'; // 2^n - 1
	func(1, 3, n);
	
	return 0;
}