[BOJ]1914 하노이 탑

• 하노이탑 문제[재귀]
  재귀로 유명한 하노이탑 문제다.
  1번 영역 / 2번 영역 / 3번 영역
  1번 영역에 쌓인 N층의 탑을 3번 영역으로 옮기는 문제
• base condition
  N = 1 -> 1번 영역의 쌓인 1층 탑을 3번 영역으로 이동$(move)$시킨다.
• 풀이의 세가지 과정

1. 1번 영역의 N-1개 층을 2번으로 이동$(hanoi)$
2. 1번 영역의 1개 층(최하층)을 3번으로 이동$(move)$
3. 2번 영역의 N-1개 층을 3번으로 이동$(hanoi)$
   위 과정을 재귀 코드로 구현

• 본 문제의 함정
  $1 <= N <= 100 => pow(2, 100) = ERR$
  $unsigned long long int$의 범위로도 해결하지 못함
  $pow()$는 double을 리턴하므로, 이와 string을 연계한 문제 풀이 수행
  .[소수점]을 기준으로 정수 값 분리 후, 해당 값에서 -1을 한 값이 정답

#include <bits/stdc++.h>
using namespace std;
int N;
void move(int n, int start, int end){
    cout << start << ' ' << end << '\n';
}
void hanoi(int n, int start, int end, int sub){
    if(n == 1) {
        move(1, start, end);
        return;
    }
    hanoi(n-1, start, sub, end);
    move(1, start, end);
    hanoi(n-1, sub, end, start);
}
int main(){
    //unsigned long long int의 범위를 벗어난다(pow(2, 100) => 다른방식 필요)
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    string s = to_string(pow(2, N));
    int finddot = s.find('.');
    s = s.substr(0,finddot);
    s[s.length() -1] -= 1;
    cout << s << '\n';
    if(N <= 20) hanoi(N, 1, 3, 2);
    return 0;
}