BOJ 1914번 하노이 탑

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

github : https://github.com/junho0956/Algorithm/tree/master/1914

 

N 이 클경우 long long 으로도 표현못한다는 것을 알고 스트링으로 구현하였습니다.

구현하고 나니 to_string 이라는 좋은 함수가 있다는걸 알게되었습니다...............

 

하노이의 경우는 https://junho0956.tistory.com/33에서 설명하였습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
 
long long dp[22];
int N;
 
void hanoi(int cnt, int to, int from, int no) {
    
    if (cnt == 1) {
        cout << to << " " << from << "\n";
        return;
    }
 
    hanoi(cnt - 1, to, no, from);
    hanoi(1, to, from, no);
    hanoi(cnt - 1, no, from, to);
}
 
void solve(int len, string str) {
 
    if (len == N) {
        int carry = 0;
        int idx = str.length() - 2;
        if (str[str.length() - 1] == '0') {
            str[str.length() - 1] = '9';
            carry = 1;
        }
        else str[idx + 1] = ((str[idx + 1] - '0') - 1) + '0';
        while (carry) {
            if (str[idx] == '0') str[idx--] = '9';
            else {
                str[idx] = ((str[idx] - '0') - 1) + '0';
                carry = 0;
            }
        }
 
        for (int i = 0; i < str.length(); i++) cout << str[i];
        cout << "\n";
        return;
    }
 
    string str2;
    int carry = 0;
    for (int i = str.length() - 1; i >= 0; i--) {
        int num = str[i] - '0';
        int makenum = num * 2 + carry;
        if (makenum > 9) carry = 1, makenum %= 10;
        else carry = 0;
        str2 += makenum + '0';
    }
 
    if (carry) str2 += 1 + '0';
    reverse(str2.begin(), str2.end());
 
    solve(len + 1, str2);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> N;
    dp[1] = 1, dp[2] = 3, dp[3] = 7;
    for (int i = 4; i <= 20; i++) dp[i] = pow(2, i) - 1;
 
    if (N <= 20) {
        cout << dp[N] << "\n";
        hanoi(N, 1, 3, 2);
    }
    else {
        int cnt = 0;
        string str;
        long long num = dp[20] + 1, num2 = dp[20] + 1;
        while (num) {
            num /= 10, cnt++;
        }
        int val = pow(10, cnt-1);
        while (num2) {
            str += (num2 / val) + '0', num2 %= val, val /= 10;
        }
 
        solve(20, str);
    }
 
    return 0;
}