백준 11729 하노이 탑 이동 순서 혼내주기

 

머리가 잘 안돌아가서 4번째까지 순서를 적어보니 규칙이 보였다. 1번에서 3번 장대로 원판 4개를 옮겨야 한다면 1번에서 2번으로 위의 3개 원판을 옮기고 가장 큰 원판을 1번에서 3번으로 옮긴 후, 2번에서 3번으로 다시 3개의 원판을 움직이면 된다. 이 과정을 n개에 대해서 수행하는 함수를 작성하면 된다.

 

#include <cstdio>

void moveN(int from, int to, int tmp, int n){
    if(n == 1){
        printf("%d %d\n", from, to);
        return ;
    }
    moveN(from, tmp, to, n-1);
    moveN(from, to, tmp, 1);
    moveN(tmp, to, from, n-1);
}

int main(){
    int n, rep = 1;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) rep *= 2;
    printf("%d\n", rep-1);
    moveN(1, 3, 2, n);

}