[BOJ] 1914 - 하노이 탑

문제 : https://www.acmicpc.net/problem/1914

---

[알고리즘풀이]

하노이 탑의 이동 횟수를 계산하는 함수와, 이동 과정을 보여주는 함수로 나눠서 해결할 수 있습니다.

[1]

하노이 탑의 이동 횟수는 H[n] = 2 * H[n-1] + 1 점화식을 이용해서 구하면 되는데,

N이 최대 100으로 N이 커지면 long long 의 범위로도 답을 담을 수 없습니다.

따라서, string을 이용해 long long 범위를 벗어나는 덧셈을 해결할 수 있었습니다.

[2]

이동 과정을 보여주는 함수는 / 얼마만큼의 원판을 / 어디서 / 어디를 이용해 / 어디로 보낼지 / 4개의 값을 이용해

재귀적으로 쉽게 구현할 수 있습니다.

#include<iostream>

using namespace std;

string h[101] = { "0", "1", };

string string_sum(string a, string b) {
	string answer ="";
	int up = 0;
	for (int i = a.length() - 1; i >= 0; i--) {
		if (i == a.length() - 1) {
			int temp = (a[i] - '0') + (b[i] - '0') + 1;
			up = temp / 10;
			temp -= 10 * up;
			answer += (char)(temp + '0');
		}
		else{
			int temp = (a[i] - '0') + (b[i] - '0') + up;
			up = temp / 10;
			temp -= 10 * up;
			answer += (char)(temp + '0');
		}
	}
	if (up != 0)
		answer += (char)(up + '0');
	string ret="";
	for (int i = answer.length() - 1; i >= 0; i--)
		ret += (char)answer[i];
	return ret;
}

void hanoi(int n, char a, char b, char c) {
	if (n == 1) {
		cout << a << ' ' << c << '\n';
		return;
	}
	hanoi(n - 1, a, c, b);
	hanoi(1, a, b, c);
	hanoi(n - 1, b, a, c);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++)
		h[i] = string_sum(h[i - 1], h[i - 1]);
	cout << h[n] << '\n';
	if (n > 20)
		return 0;
	hanoi(n, '1', '2', '3');
	return 0;
}

---