하노이 탑 C++ - 백준 1914

https://acmicpc.net/problem/1914

하노이 탑 재귀 알고리즘을 아는지 물어보는 문제였다.

이 문제에서의 걸림돌은 큰 수를 처리하는 과정이었다.

long long 자료형은 절댓값 2**63-1 까지 저장할 수 있기 떄문에

long long으로는 턱없이 부족하여 pow함수를 직접 구현하는 것이 아닌

cmath에 있는 pow 함수를 사용해야했다.

pow를 사용하면 매우 큰 수는 실수형으로 반환되고 소수점 올림 처리가

되기 때문에 소수점을 지워주고, -1을 해주어야 한다.

코드는 다음과 같다.

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

int n;
vector<pair<int, int>> ans;

void hanoi(int n, int from, int to, int other){
	if(n==0){
		return;
	}
	hanoi(n-1,from,other,to);
	ans.push_back({from,to});
	hanoi(n-1,other,to,from);
}

int main(){
	cin >> n;
	string s=to_string(pow(2,n));
	int x=s.find('.');
	s=s.substr(0,x);
	s[s.length()-1]-=1;
	cout << s << '\n';
	if(n<21){
		hanoi(n,1,3,2);
		for(int i=0;i<ans.size();i++){
			cout << ans[i].first << ' ' << ans[i].second << '\n';
		}
	}
}