(cpp) Baekjoon 11729번 문제 ‘하노이 탑 이동 순서’ - 재귀

06 Dec 2022 on Programming Languages

Baekjoon 11729번 문제 ‘하노이 탑 이동 순서’ - 재귀

---

문제

풀이

# define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cmath>
using namespace std;

int n;

void hanoi(int n, int start, int storage, int target) {
	if (n == 1) {
		cout << start <<" " << target<<"\n"; // 가장 큰 1개(n-1개 이동시키고 남은 1개)는 target으로
	}

	else {
		hanoi(n - 1, start,target, storage); //n-1개를 storage로 이동
		cout << start <<" " << target<<"\n";
		hanoi(n - 1, storage, start, target); //storage에 있는 n-1개를 target으로 이동
	}

}

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