백준 1914번 하노이 탑

백준 1914번 하노이 탑

#include <iostream>
#include <queue>
#include<stack>
#include <cmath>
#include<string>
#include<vector>
#include<algorithm>
#include <cstring> //memset
using namespace std;
 
 
int ret;
 
vector<pair <int, int> > v;
 
 
void Hanoi(int n, int from, int by, int to) {
    if (n == 1) {
        v.push_back({ from,to });
    }
    else {
        Hanoi(n - 1, from, to, by);
        v.push_back({ from,to });
        Hanoi(n - 1, by, from, to);
    }
 
}
 
string bigNum(string n1, string n2) {
    long long sum = 0;
    string result;
 
    while (!n1.empty() || !n2.empty() || sum) {
        if (!n1.empty()) {
            sum += n1.back() - '0';
            n1.pop_back();
 
        }
        if (!n2.empty()) {
            sum += n2.back() - '0';    
            n2.pop_back();
        }
        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
    reverse(result.begin(), result.end());
    return result;
}
string subone(string num) {
    int back = num.back()-'0';
    num.pop_back();
    back -= 1;
    num.push_back(back + '0');
    return num;
}
 
 
int main(void){
 
    int n;
    cin >> n;
 
 
    if (n <= 20) {
        cout << (long long)pow(2, n) - 1 << "\n";
        Hanoi(n, 1, 2, 3);
        for (int i = 0; i < v.size(); i++) {
            cout << v[i].first << " " << v[i].second << "\n";
        }
    }
    else {
        string num = "2";
        for (int i = 0; i < n - 1; i++) {
            string temp = bigNum(num, num);
            num = temp;
            
        }
        cout << subone(num) << "\n";
        
 
    }
    
 
    return 0;
}

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

코드 보고 똑같이 적어서 풀었습니다..

https://jaimemin.tistory.com/732 

코드 참조

획기적인 알고리즘 사용이 아니라 큰 수 처리를 잘 해주는 것이 관건이였네요..