[BOJ] 1914번 : 하노이 탑

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
string multiply(string a, string b) {
	int n = a.size();
	int m = b.size(); 
	vector<int> result(n + m, 0); // a자리 * b자리 최대수는 a+b자리 

	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			int mul = (a[i] - '0') * (b[j] - '0'); 
			int sum = mul + result[i + j + 1]; 
			result[i + j] += sum / 10; 
			result[i + j + 1] = sum % 10; 
		}
	}
	string product; 
	for (int num : result) {
		if (!(product.empty() && num == 0)) {
			product.push_back(num + '0');
		}
	}
	return product.empty() ? "0" : product;
}
string power_of_two(int exponent) {
	string result = "1";
	string base = "2";

	for (int i = 0; i < exponent; i++) {
		result = multiply(result, base);
	}

	return result;
}
void hanoi(int k, int a, int b) {
	if (k == 0) return; 
	hanoi(k - 1, a, 6 - a - b);
	cout << a << ' ' << b << '\n'; 
	hanoi(k - 1, 6 - a - b, b);
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	if (n <= 63) {
		unsigned long long total_cnt = (1ULL << n) - 1; 
		cout << total_cnt << '\n'; 
	}
	else {
		string total_cnt = power_of_two(n);
		total_cnt[total_cnt.size() - 1] -= 1; 
		cout << total_cnt << '\n';
	}
	if (n <= 20) hanoi(n, 1, 3);

}

큰 수를 다루는 법칙 꼭 기억하자..!