Baekjoon 1914번 하노이 탑

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

int main(){
    fastio;
    int n;
    cin >> n;
    string ans = to_string(pow(2, n));
    int idx = ans.find('.');
    ans = ans.substr(0, idx);
    ans[ans.length()-1] -= 1;
    cout << ans << "\n";
    if(n <= 20) hanoi(n, 1, 2, 3);
    return 0;
}

c++ 은 bigInteger 자료형을 지원해주지 않는다. 20이 넘는 하노이 탑의 최소 이동횟수를 구하려면 long long 의 범위를 넘는 값을 출력해야하는데 string 을 이용한 방법이 존재했다. pow 함수의 계산값을 to_string 함수를 이용해 문자열로 바꾸어주면 자리수에 상관없이 숫자를 문자열로 표현할 수 있다. string 의 find 메소드를 이용하여 소수점 이하 자리수를 제거해주면 끝이다. 하노이탑의 최소 이동횟수는 2ⁿ-1 이므로 문자열의 마지막 문자 아스키코드 값을 1 줄여주면 된다. (2의 제곱수는 0으로 끝나는 수가 존재하지 않는다.)