[BOJ] 백준 1914 하노이 탑

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

 Input 
3　 

 Output 

7

1 3

1 2

3 2

1 3

2 1

2 3

1 3

Sample Output을 분석하면 어떻게 옮겨지는지 알 수 있습니다.

이를 재귀적으로 해결할 수 있습니다.

1. 제일 큰 원반을 제외한 N-1개의 원반들을 A 기둥에서 B 기둥으로 이동시킵니다.

2. 제일 큰 원반 한개를 A 기둥에서 C 기둥으로 이동시킵니다.

3. 1번에서 옮겨진 원반들을 B기둥에서 C 기둥으로 이동시킵니다.

    : 시작점과 도착점이 있고, 도달하기 위한 중간점을 이용해야만 합니다.

 

문제조건상 N > 20인 경우는 원반들이 옮겨지는 횟수만 구하면 되는데

결국 (2N - 1)을 출력하면 됩니다.  ← 수학적으로 증명

하지만 2100은 long long 자료형으로도 표현할 수 없기 때문에

string을 통해 Big Integer를 구현해서 처리합니다.

---

#include <cmath>
#include <string>
#include <iostream>
using namespace std;

string bigSum(string s1, string s2) {
    int carry = 0;
    string ans = "";
    for (int i = s1.size() - 1; i >= 0; i--) {
        int sum = s1[i] - '0' + s2[i] - '0' + carry;
        carry = sum / 10;
        ans = to_string(sum % 10) + ans;
    }
    if (carry) {
        ans = '1' + ans;
    }
    return ans;
}

void hanoi(int n, int from, int other, int to) {
    if (n == 0) {
        return;
    }

    hanoi(n - 1, from, to, other);
    printf("%d %d\n", from, to);
    hanoi(n - 1, other, from, to);
}

int main(void) {
    int n; cin >> n;
    if (n <= 20) {
        printf("%d\n", (int)pow(2, n) - 1);
        hanoi(n, 1, 2, 3);
        return 0;
    }
    
    // n > 20인 경우
    string ans = "2";
    for (int i = 0; i < n - 1; i++) {
        ans = bigSum(ans, ans);
    }
    ans[ans.size() - 1] -= 1;
        
    cout << ans;    
}