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

문제 이해

- 3개의 장대가 존재한다.

- 첫 번째 장대에 n개의 원판이 내림차순으로 쌓여있다.

- 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려고 한다.

- 규칙

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

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

- 필요한 이동 순서의 최솟값을 출력하라.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 256MB

 

<입력>

- N: 첫 번째 장대에 쌓인 원판의 개수 (1 ~ 20)

 

<출력>

K: 옮긴 횟수

A, B: 수행 과정, A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻

 

 

---

문제 풀이

n의 범위가 20까지인걸로 보아 재귀 형태로 푸는 문제 같았다.

 

문제는 거기서 멈췄다는 것...

구현을 도저히 생각해낼 수 없었다.

스택을 3개 사용하는 문제인가 싶었지만 너무 난해했다.

 

결국 

https://codesyun.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11729%EB%B2%88-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C-C-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

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

이 분의 포스트를 참고했다.

 

 

그래도 설명해보자면

이 문제는 하노이 탑의 원리에 대해 알고 있어야 하는 문제였다.

1. n-1개의 원판을 3번째 장대를 거쳐 2번째 장대로 옮긴다.

2. 1번째 장대에 있는 가장 큰 크기의 원판을 3번으로 옮긴다.

3. 2번째 장대에 있는 n-1개를 1번째 장대를 거쳐 3번으로 이동시킨다.

 

 

이 원리를 재귀로 표현하면 된다!

void solve(int start, int mid, int end, int n){
    if(n == 1){
        cout<<start<<" "<<end<<"\n";
    }else{
        solve(start, end, mid, n-1);
        cout<<start<<" "<<end<<"\n";
        solve(mid, start, end, n-1);
    }
}

 

그리고 하노이 탑의 최소 이동 횟수는 2 ^ n -1이다.

이것도 그냥 외우면 좋을 듯 싶다.

 

 

최소 이동 횟수를 구하며 pow 함수를 쓸 경우 주의할 점이 있는데

return형이 double이므로 값이 커지면 오차가 발생한다.

 

int형으로 캐스팅해서 오차가 생기지 않도록 하자.

cout<<(int)pow(2, n) - 1<<"\n";

 

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

void solve(int start, int mid, int end, int n){
    if(n == 1){
        cout<<start<<" "<<end<<"\n";
    }else{
        solve(start, end, mid, n-1);
        cout<<start<<" "<<end<<"\n";
        solve(mid, start, end, n-1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    cout<<(int)pow(2, n) - 1<<"\n";
    solve(1, 2, 3, n);
    
    return 0;
}

 

 

 

---

배운 점

재귀는 역시 어렵다...

 

하노이 탑의 원리와 최소 이동 횟수에 대해 배울 수 있었던 문제였으며,

pow 함수를 쓸 때 주의할 점도 배울 수 있었다!