11729 하노이 탑

접근

장대 1, 2, 3이 있고, 1에 원판 3개가 있을 때,
이 원판을 모두 크기 순에 맞게 장대 3에 옮겨야 한다.

그 과정을 살펴보자.
a b 는 a의 맨위의 원판을 b의 맨 위로 옮긴다는 뜻이다.

자 머리속으로 상상해보자. 그러면서 일반화 해보자.(n개의 원판으로!)

1 3
1 2
3 2 ---------- 1) 지금 이상황은 1에서 제일 큰 원판이, 2에 n-1개의 원판이 순서대로 있는 상황이다.

1 3 ---------- 2) 1에 있는 가장 큰 원판을 3으로 보낸다.

2 1
2 3
1 3 ---------- 3) 2에서 n-1개의 원판을 3으로 보내는 상황이다.

함수 f(a, b, n_disk)를 정의하고
맨처음 상황을 f(1, 3, 3)으로 생각해보자.
1)의 상황을 다시 한번 보자.
f(1, 2, 2) 이다.
1 3 ------- 1-1) f(1, 3, 1)

1 2 ------- 1-2) print("1 2")

3 2 ------- 1-3) f(3, 2, 1)

이제 감이 좀 잡혔을 것이다.

f(a, b, n_disk)는
f(a, c, n_disk - 1)
print("a b")
f(c, b, n_disk - 1)
이다.


이제 이것을 잘 조작해서 코드를 만들면 된다.

하노이탑 횟수를 먼저 출력해야 하므로, (print할 때마다 count를 추가하려 했지만, 맨 처음에 출력할 수 없어서..)
규칙을 발견해보자.
1일때 1
2일때 3
3일때 7
4일때 ....
뭐 이렇게 해도 되고,

 

이를 이용해서,

임을 알 수도 있다.

이것을 빠른 시간 출력하기 위해서는, << 연산자를 잘 이용해 보자!

 

#include <cstdio>
void hanoi(int a, int b, int n_disk){
    if (n_disk == 0) return;
    hanoi(a, 6 - a - b, n_disk - 1);
    printf("%d %d\n", a, b);
    hanoi(6 - a - b, b, n_disk - 1);
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", (1 << n) - 1);
    hanoi(1, 3, n);
    return 0;
}