11729번

11729번 - 하노이 탑 이동 순서

하노이하면 가장 먼저 떠오르는게 재귀인데..

나는 사실 하노이에 대해서 어떻게 푸는지 몰랐다.. 백지 상태에서 풀려는데 너무 어려워서

검색을 통해서 하노이에 대해서 공부를 먼저 했다. 재귀는 역시 이해하기가 어렵긴 한데..

N-1 개 옮기고, 1개 옮기고, N-1 개 다시 옮기는게 그냥 핵심이었다.

그 과정에서 N==1 일때만 잘 체크해주면 되는 재귀함수였다.

코드에서 ans 를 구하는 방식을 2^N - 1을 썼는데 이는 하노이탑에서 경우의 수를 구하는 방법이다.

이 과정은 점화식 N개 원반을 몇번 움직여서 다 옮길 수 있는가

D[N] = D[N-1] + 1 + D[N-1] 로 놓고 DP 로 구할 수 있다.

## 이 문제는 cout 이 아닌 printf 를 써야만 시간초과가 되지 않고 AC를 받을 수 있는 문제였다.

<정답 코드>

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
 
void hanoi(int n, int start, int by, int dest)
{
    if (n == 1)
    {
        printf("%d %d\n", start, dest);
        return;
    }
 
    hanoi(n - 1, start, dest, by);
    hanoi(1, start, by, dest);
    hanoi(n - 1, by, start, dest);
}
 
 
int main()
{
    int N;
    int ans;
    cin >> N;
 
    ans = pow(2, N) - 1;
 
    printf("%d\n", ans);
 
    hanoi(N, 1, 2, 3);
 
    return 0;
}