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

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

11729번: 하노이 탑 이동 순서

[소스코드]

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
// [baekjoon] 11729번 - 하노이 탑 이동 순서
// 2023.01.31

string str;

void hanoi(int n, char from, char aux, char to) {
	if (n == 1) {
		cout << from << " " << to << "\n";
		return;
	}
	hanoi(n - 1, from, to, aux);
	cout << from << " " << to << "\n";
	hanoi(n - 1, aux, from, to);
}

int main() {

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	cout << (int)pow(2, n) - 1 << '\n';

	hanoi(n, '1', '2', '3');

	return 0;
}

재귀를 이용하여 하노이탑 문제를 풀어내는 방법은 많이 알려져 있습니다.

 

다만 이 문제에서는 가장 먼저 옮긴 횟수 K를 물어보는데요,

재귀 과정에서 K를 계산하려고 하면 굉장히 어려워 집니다.

 

해결 방법은 간단합니다.

하노이탑의 최소 이동횟수 K = 2^n - 1

이라는 사실을 이용하면 재귀 과정에서 K를 굳이 세지 않아도 쉽게 풀 수 있습니다.