[BOJ 11729] 하노이 탑 이동 순서

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

우리가 평소에 알고 있던 하노이 탑을 이동시키며 그 경로를 출력하는 문제이다. 처음 문제를 보았을때는 시뮬레이션 해보며 특정순서에는 특정 규칙에 따라 이동을 한다고 생각하였는데 .... 뭔가 삽질을 하는것 같았다. 

해당문제는 분할정복, 즉 dnc로 접근을 해볼 수 있다. 

해당 하노이의 탑에서 1번에서 3번으로 옮기려면 어떤 과정을 거쳐야 할까? n개의 탑을 옮기기 위해서는 먼저 1번부터 n-1번까지 2번으로 옮기고, n번째 탑을 3번으로 옮기고, 1부터 n-1개의 탑을 3번으로 옮기면 된다. 

정리를 하자면 solve(n,x,y) 는 solve(n-1,x,6-x-y)  후 n번째 판을 3번으로 옮기고, solve(n-1,6-x-y,y) 를 해주면 되는것이다.

#include <cstring>
#include <iostream>
#include <math.h>
#include <cstdio>
using namespace std;
 
int n,ans;
void solve(int n,int x,int y){
    if(n == 0)return ;
    solve(n-1,x,6-x-y);
    printf("%d %d\n" , x,y);
    solve(n-1 , 6-x-y,y);
    
}
int main(){
    ans = 0;
    scanf("%d" , &n);
    int a = pow(2,n) -1;
    printf("%d\n" ,a);
    solve(n,1,3);
    return 0;
}

이런식으로 간단하게 해결을 할 수 있다. 하노이의 탑의 일반항은 a(n) = 2^n -1 인데 증명은 http://cafe.naver.com/spielmathe/12674  를 참고하면 좋을것이다.