11729번: 하노이 탑 이동 순서

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


$O(2^n)$

f(x,y,k)를 호출하면 1~k번째 원판을 x위치에서 y위치로 옮기는 일을 수행한다고 하자.
f(x,y,k)는 다음 행동과 같다.

x,y가 아닌 위치(1,2,3 중 하나)를 z(=6-x-y)라 하자.
1. 1~k-1번째 판을 x에서 z로 옮긴다. = f(x,z,k-1)
2. k번째 판을 x에서 y로 옯긴다.
3. 1~k-1번째 판을 z에서 y로 옮긴다. = f(x,y,k-1)

따라서 재귀호출을 이용해 간단히 구현할 수 있다.
n개 판을 이동시키는데 2^n-1번의 이동이 필요함은 수학적 귀납법으로 쉽게 증명할 수 있다.
-> 2^n-1 = 2^(n-1)-1 + 1 + 2^(n-1)-1

#include<cstdio>
int n;
void f(int x, int y, int z) {
    if (!z) return;
    f(x, 6 - x - y, z - 1);
    printf("%d %d\n", x, y);
    f(6 - x - y, y, z - 1);
}
int main() {
    scanf("%d", &n);
    printf("%d\n", (1 << n) - 1);
    f(1, 3, n);
    return 0;
}