[백준] 1914번 : 하노이 탑 - 재귀, 큰 수

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

1914번: 하노이 탑

큰 수의 계산을 잘 구현해야 하는 문제이다.

2^100은

10^34 정도 되기 때문에

long long 은 최대 19자리이므로 long long 2개를 붙여쓰면 38자리까지 구현이 가능하다.

 

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


void _pow(int n){
    long long a = 0, b = 0, mod = 1'000'000'000'000'000'000;
    for(int i=0; i<n; i++){
        b*=2;
        a = 2 * a + 1;
        b += a / mod;
        a %= mod;
    }
    if(b>0) cout << b << a << '\n';
    else cout << a << '\n';
}


//start : 0 , mid:1, end:2
void moveBlock(int start, int end){
    cout << start+1 << ' ' << end+1 << '\n';
}


void hanoi(int n, int start, int mid, int end){
    if(n==0) return;
    hanoi(n-1, start, end, mid);
    //마지막꺼 옮기기
    moveBlock(start, end);
    hanoi(n-1, mid, start, end);
}

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

    int n;
    cin >> n;
    _pow(n);

    if(n<=20) {
        hanoi(n, 0, 1, 2);
    }

    return 0;
}