백준, BOJ, 하노이 탑 이동 순서, 11729번 C++ [CPP] **

하노이 탑의 근본을 알려주는 문제다

 

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

11729번: 하노이 탑 이동 순서

 

---

 

하노이 탑하면 재귀문제가 떠오른다.

하지만 감은 전혀 안 온다.

 

아니 감이 안 온다기보다는 코딩을 못하는 것이다.

머리로는 이해가 가는데.. 코딩을 어떻게 해야하지??

나도 그렇다. 아직 재귀가 익숙치 못하다.

 

하나씩 알아보자

여기 링크 들어가서 알아보자

https://www.mathsisfun.com/games/towerofhanoi.html

Play Tower of Hanoi

 

원판 1개

기둥 1에서 기둥 3으로 옮기려고 한다.

 

1 -> 3 (크기 1 이동)

 

원판 2개

1 -> 2 (크기 1 이동)

1 -> 3 (크기 2 이동)

2 -> 3 (크기 1 이동)

 

원판 3개

1 -> 3 (크기 1 이동)

1 -> 2 (크기 2 이동)

3 -> 2(크기 1 이동)

1 -> 3 (크기 3 이동)

2 -> 1 (크기 1 이동)

2 -> 3 (크기 2 이동)

1 -> 3 (크기 1 이동)

 

얘는 그림도 같이보자

1

2

 

3

 

4

5

 

6

 

7

 

 

뭔가 보일 것 같은데???

색을 보면

뭔가 느껴질 듯 싶다.

 

다시 생각해보자

3개를 생각해보자

 

원판 3개를 1에서 3으로 옮기려면

 

1. 원판 2개를 1에서 2로 옮겨야한다.

2. 원판 크기 3을 1에서 3으로 옮긴다.

3.. 그 후 원판 2개를 2에서 3으로 옮기면 된다.

 

1. 원판 2개를 1에서 2로 옮기려면

1-1 원판 크기 1을 1에서 3으로 옮겨야 한다.

1-2 원판 크기 2를 1에서 2로 옮긴다.

1-3 원판 크기 1을 3에서 2로 옮긴다. 

 

3. 원판 2개를 2에서 3으로 옮긴다.

3-1 원판 크기 1을 2에서 1로 옮긴다.

3-2 원판 크기 2를 2에서 3으로 옮긴다.

3-3 원판 크기 1을 1에서 3으로 옮긴다.

 

 

** 원판 크기 별로 보자.

 

 

 

 

??? 흠.. 

원판 N개를 1에서 3으로 옮기려면?

원판 N-1개를 1에서 2로 옮겨야 한다..?

그 후 크기 N을 1에서 3으로 옮기고?

N-1을 2에서 3으로 옮겨야 한다..?

 

여러번 풀다보면 익혀진다는 선배님들의 말씀을 받들어 읽어보고 풀어보고 느껴보자

 

-> N-1개를 목표기둥이 아닌 다른 기둥으로 옮겨야 N개를 목표 기둥으로 옮길 수 있게 된다.

 

 

점화식을 구했다.

 

초항도 구해보자

원판 1개를 1에서 3으로 옮기는 것은..??

그냥 된다.

 

여기서 아이디어가 나온다.

 

맞는 풀이

#include<iostream>

using namespace std;

//a에서 b로 n개 원판 이동
void func(int a, int b, int n){
    //1일 때 1에서 3으로 이동하면 끝
    if(n == 1){
        cout << a << ' ' << b << "\n";
        return;
    }
    //3개의 기둥 기둥 번호의 합은 6
    //a가 출발, b가 도착이면 남은 기둥의 번호는 6-a-b
    func(a, 6-a-b, n-1);
    cout << a << ' ' << b << "\n";
    func(6-a-b, b, n-1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int k;
    cin >> k;
    cout << (1<<k) - 1 << "\n";
    func(1,3,k);
}