[백준/C++] 1914번: 하노이 탑

문제

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

1914번: 하노이 탑

---

문제 요약

세 개의 장대가 있을 때, 첫 번째 장대에 반경이 서로 다른 n개의 원판이 쌓여 있다.

각 원판은 반경이 큰 순서대로 쌓여 있다.

 

규칙에 따라. 첫 번째 장대에 있는 n개의 원판을 모두 세 번째 장대로 옮길 때, 옮긴 횟수와 순서를 출력한다.

 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

단, 이동 횟수는 최소가 되어야 한다.

---

코드

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

int n;

int arr[4];

// n개의 원판을 A번째 탑에서 B번째 탑으로 이동
void go(int n, int A, int B) {
    // 한 개의 원판 옮기기 구현
    if (n == 1) {
        arr[A]--;
        arr[B]++;
        cout << A << " " << B << "\n";
        return;
    }

    int C; // 현재 n-1개의 원판을 임시로 옮겨둘 탑의 위치

    if ((A == 1 && B == 2) || (A == 2 && B == 1)) {
        C = 3;
    }
    else if ((A == 1 && B == 3) || (A == 3 && B == 1)) {
        C = 2;
    }
    else {
        C = 1;
    }

    go(n - 1, A, C); // C로 n-1개의 원판을 임시로 옮겨두고,
    go(1, A, B); // B로 1개의 원판을 옮긴다.
    go(n - 1, C, B); // C에 임시로 뒀던 n-1개의 원판을 B로 옮긴다.
}

int main() {
    // 입출력 시간 단축
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    // long long 자료형의 범위를 넘으므로 string(pow)을 이용
    string cnt = to_string(pow(2, n)); 

    // pow는 실수형을 반환하므로 소수점 위치를 파악 후, 소수점 아래 자리 제거
    int dot_idx = cnt.find('.'); 
    cnt = cnt.substr(0, dot_idx);

    // 2^n - 1이 옮긴 횟수이므로 -1 진행
    cnt[cnt.length() - 1] -= 1; // 아스키코드 -1
    cout << cnt << "\n";


    // 1번 탑에 n개 원판 존재
    arr[1] = n;

    // n개의 원판을 1번 탑에서 3번 탑으로 이동
    if (n <= 20) go(n, 1, 3); 

    return 0;
}

---

코드 설명

하노이 탑 문제에서 A번 탑에서 B번 탑으로 n개의 원판을 옮기기 위한 풀이는 다음과 같다.

1. A번 탑에 있는 n-1개의 원판을 A번 탑도, B번 탑도 아닌 C번 탑에 임시로 옮긴다.

2. A번 탑에 남아 있는 1개의 원판을 옮기고자 하는 B번 탑에 옮긴다.

3. C번 탑에 임시로 옮겼던 n-1개의 원판을 B번 탑에 옮긴다.

 

따라서, n개의 원판을 옮기기 위해서는 n-1개의 원판 옮기는 방법을 알아야 하고, 다시 n-2개의 원판 옮기는 방법, ... , 1개의 원판을 옮기는 방법을 알아야 한다.

 

=> 이를 재귀로 구현한다.

 

처음에는 dp를 이용하여 문제를 해결하려 했지만, 실패했다.

dp[1] = 1;

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] * 2 + 1;
}

 

위 식처럼, n개의 원판을 옮기는 데 필요한 횟수는 2^ n - 1이고,

 

n이 100까지 가능하므로, 우리가 알고 있는 자료형으로는 표현이 불가하다.

 

따라서, string과 pow 함수를 이용한다.

 

먼저, pow(2, n)로 반환된 값을 to_string 함수를 사용하여 string으로 변환하여 표현이 불가능한 큰 수를 문자열로 저장한다.

 

이때, pow 함수의 반환 값은 실수형이므로, find 함수를 이용하여 소수점 위치를 파악하고, substr을 이용하여 소수점 아래 부분을 제거한다.

 

마지막으로, 마지막 인덱스에 해당하는 문자의 아스키코드에서 -1을 한다.

+ 2의 제곱수 중 1의 자리가 0인 수는 없으므로 가능하다.