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

문제

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

백준 11729

 

문제 내용

하노이 탑을 하는데, n개의 원판을 3번 기둥으로 옮기는 최소 이동 횟수와 수행 과정을 출력하면 된다.

 

문제 풀이

먼저 수행 과정은 재귀를 통해 풀 수 있다. 

n개의 원판을 1에서 3으로 옮긴다면,

1. n-1개의 원판을 기둥 1에서 2로 옮긴다.
2. n번 원판을 기둥 3으로 옮긴다.
3. n-1개의 원판을 기둥 2에서 3으로 옮긴다.

원판이 1개일 때는 당연히 기둥에서 기둥으로 옮길 수 있다.

 n==1일 때도 성립하고, n개일 때도 성립하니 n+1일 때도 성립한다고 볼 수 있다. (== 재귀로 풀 수 있다)

 

이동 횟수를 구하는 부분은 수학적 지식이 조금 필요하다.

이동 횟수는 n-1개의 원판을 1에서 2로 옮길 때 A번, 2에서 3으로 옮길 때 A번, 그리고 n번 원판을 3번 기둥으로 옮길 때 1번 필요하다. 

즉, n개의 원판을 이동하려면 2A+1번의 이동이 필요하다. (A는 n-1개 원판의 이동 횟수)

원판 1개를 이동하는 데에는 당연히 1번의 이동이 필요하다.

위 정보를 식으로 정리하여 풀이하면 아래 사진처럼 풀이할 수 있다. (등비수열의 합 공식을 알아야 한다.)

이동 횟수 풀이

 

코드

#include <iostream>
using namespace std;

/**
 * n-1개의 원판을 기둥 1에서 기둥 2로 옮긴다.
 * n번 원판을 기둥 3으로 옮긴다.
 * n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.
 *
 * - 원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때에도 옮길 수 있다.
 * - 원판이 1개일 때에 옮길 수 있다.
 *
 * => 재귀로 풀 수 있다.
 */
void hanoi(int a, int b, int n) { // a번 막대에서 b번 막대로 n개를 옮길 때의 이동 횟수
    if (n == 1) {
        cout << a << ' ' << b << '\n';
        return;
    }

    hanoi(a, 6 - a - b, n - 1);
    cout << a << ' ' << b << '\n';
    hanoi(6 - a - b, b, n - 1);
}

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

    cout << (1 << n) - 1 << '\n'; // 2^n-1 개
    hanoi(1, 3, n);
}