BaekJoon(11729)::하노이의 탑 이동 순서

문제

11729번: 하노이 탑 이동 순서

문제파악

• 하노이 탑의 이동 원리 파악 → 출력
• 하노이 탑의 이동 횟수 → 재귀식을 일반항으로 도출하여 주워진 판의 갯수를 통해 총 이동횟수를 알 수 있다.

문제풀이

1. 하노이 탑의 이동횟수 → $a_n = 2^n-1$
2. 각 하노이의 마지막 판의 이동을 출력

#include <iostream>
#include <cmath>
using namespace std;

void hanoi(int n, int from, int via, int to) {
    if (n == 1) {
        printf("%d %d\n", from, to);
        return;
    }

    hanoi(n - 1, from, to, via);
    printf("%d %d\n", from, to);
    hanoi(n - 1, via, from, to);
    return;
}

int main()
{
    int n;
    cin >> n;

    printf("%d\n", (int)pow(2, n) - 1);

    hanoi(n, 1, 2, 3);
    return 0;
}

주의할 점

1. 출력 시간 단축 → cout, endl를 이용하여 출력시 시간초과 발생, printf 추천
2. pow의 return 타입이 float로 틀린 결과가 나옴. 즉, 형변환을 해줘야한다.