1914번 하노이 탑

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

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

하노이 탑 문제이다. 

Biginteger 부분의 코드도 알아야겠다.

원리는 (기둥 1에서 출발 가정)

기둥 1, 기둥 2, 기둥 3이 있을 때, 순서대로 요약하자면

기둥 1의 맨 위에 있는 (N - 1)개를 기둥 2로 옮긴다.

기둥 1에 있는 나머지 1개(가장 큰 것)를 기둥 3으로 옮긴다.

기둥 2에 있는 (N - 1)개를 기둥 3으로 옮긴다.

완성.

위를 재귀적으로 요약하면 아래와 같다.

1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.(기둥 3을 이용)

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.(기둥 1을 이용)

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int N = 0;
 
void hanoi(int cnt, int from, int path, int to)
{
    if (cnt == 1) printf("%d %d\n", from, to);
    else
    {
        hanoi(cnt - 1, from, to, path); // --cnt 안 된다.
        printf("%d %d\n", from, to);
        hanoi(cnt - 1, path, from, to); // --cnt 안 된다.
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    string s = to_string(pow(2, N));
 
    int idx = s.find('.');
 
    s = s.substr(0, idx);
 
    s[s.length() - 1] -= 1;
 
    cout << s << '\n';
 
    if (N <= 20) hanoi(N, 1, 2, 3);
 
    return 0;
}