ascode 1103 하노이 탑

문제 설명

하노이 탑은 팩토리얼을 구하는 함수와 함께 재귀함수를 학습할 떄 주로 사용되는 유명한 예제이다.


“고대 인도 베나레스에 있는 한 사원의 이야기”
여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 63개(혹은 64개)의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다.
이 규칙으로 63(64)개의 원판을 처음 놓여있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다.


조건을 정리하자면 아래와 같다.

[아래] 한번에 하나의 원판만 이동할 수 있다.
맨 위에 있는 원판만 이동할 수 있다.
크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야한다.

위의 조건을 지키며 최소의 이동을 하였을 떄 몇 번을 이동시켜야 하는지 알아보자.

입력 설명

첫줄에 testCase의 수 T(<10)가 입력된다.

이후 T만큼 옮겨야 할 원판의 갯수 N(<=15)가 주어진다.

출력 설명

원판들을 다른 막대로 옮기는데 필요한 최소의 이동 횟수와 방법을 출력한다.

입력 예시

2
3
4 

출력 예시

원판 1을 A 에서 C로 옮긴다
원판 2를 A 에서 B로 옮긴다
원판 1을 C 에서 B로 옮긴다
원판 3를 A 에서 C로 옮긴다
원판 1을 B 에서 A로 옮긴다
원판 2를 B 에서 C로 옮긴다
원판 1을 A 에서 C로 옮긴다
7
원판 1을 A 에서 B로 옮긴다
원판 2를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
원판 3를 A 에서 B로 옮긴다
원판 1을 C 에서 A로 옮긴다
원판 2를 C 에서 B로 옮긴다
원판 1을 A 에서 B로 옮긴다
원판 4를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
원판 2를 B 에서 A로 옮긴다
원판 1을 C 에서 A로 옮긴다
원판 3를 B 에서 C로 옮긴다
원판 1을 A 에서 B로 옮긴다
원판 2를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
15

코드

#include <stdio.h>
int count = 0;
void  check(int n, char a, char b, char c) {
    if (n == 1) {
        printf("원판 1을 %c 에서 %c로 옮긴다\n", a, c);
        count++;
    }
    else {
        check(n - 1, a, c, b);
        printf("원판 %d를 %c 에서 %c로 옮긴다\n", n, a, c);
        check(n - 1, b, a, c);
        count++;
    }
}

int main()
{
    int a, b, c;
    scanf("%d", &a);
    for (int i = 0; i < a; i++)
    {
        scanf("%d", &b);
        check(b, 'A', 'B', 'C');
        c = count;
        printf("%d\n", count);
        count = 0;
    }
    return 0;
}

나 : say

꼭꼬꼮ㄲㄲ고갸ㅐㅣ로ㅜ미ㅏㄴ암너ㅏㅣㅇㅁ너ㅣㅏㅇㅁㄴ
오타를 다시한번더 확인을 하자