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

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

문제

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

풀이

분할 정복 알고리즘을 이용해서 푸는 문제입니다. 수학적 귀납법을 이용해 증명을 해보면 규칙을 발견할 수 있습니다. 

가장 먼저 출력해야 하는 이동 값은 2^n-1 입니다. 처음에 이를 math.h를 이용해서 출력하려 했는데 시간 초과가 떠서 쉬프트 연산자를 활용하여 출력했습니다.

어렵다는 생각이 들어서 case 4까지 직접 노트에 적어가면서 탑 이동을 해보았습니다.

case 1	case 2	case3	case4
1->3	1->2 -----------------  1->3 -----------------  2->3	1->3  1->2  3->2 -----------------  1->3 -----------------  2->1  2->3  1->3	1->2  1->3  2->3 -------  1->2 -------  3->1  3->2  1->2 -----------------  1->3 -----------------  2->3  2->1  3->1 -------  2->3 -------  1->2  1->3  2->3

"1번위치"에서 "3번위치"로 옮긴다고 할 때, 쪼개어보면 1~n-1까지의 탑을 2번으로  옮기고 n(맨 아래 원판)을 3번으로 옮깁니다. 다만, n값이 커지면서 케이스가 쪼개지는 것을 볼 수 있습니다. 이를 재귀를 활용하여 구하면 됩니다.

hanoi(출발지, 목적지, count값) 으로 코드를 짜면 아래와 같습니다.

코드

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