백준 하노이의 탑(11729)

문제이해

출처:https://blog.encrypted.gg/943

기둥 1에 있는 n번 원판은 3번 기둥으로 이동해야 된다

n번 원판이 이동하기 위해서는 n-1 ~ 1번까지 기둥 2번으로 이동해야 함

 

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

n번 원판을 3번으로 옮긴다.

원판이 n-1개일 때 옮길 수 있으면 n개일 때도 옮길 수 있음

n=2라고 가정하면, 기둥 1에 있는 1(n-1)개의 원판을 기둥 2번으로 옮기고 나머지 하나 남은 원판(n)도 옮길 수 있음

 

 

함수 정의 방법

원판 n개를 a에서 b로 이동하는 방법을 출력하는 함수

void func(int a, int b, int n)

 

Base condition

가장 아래에 있는 원판이 이동하려면 n=1 일때 이동 가능하므로 가장 아래에 있는 원판을 이동 후 재귀함수를 호출하지 않는다.

n=2 라고 가정을 했을 때 맨 아래에 있는 원판(2)이 움직이기 위해서 첫번째 원판(1)이 이동을 해야 하는데 최초에 n은 2인상태니까 n-1를 해줘서 맨 아래에 있는 원판(2)만 있는 경우일때만 이동할 수 있다.

 

재귀 식

기둥은 1, 2, 3 총 3개의 기둥이 있다고 가정한다.

최초 함수호출은 원판을 2개로 한다고 가정한다.

void func(1, 3, 2)

 

 

1. n-1개의 원판을 기둥 a에서 b로 옮긴다

void func(a, 6-a-b, n-1)

맨 아래에 있는 원판(2)는 a(1번 기둥)에서 b(3번 기둥)으로 가야 되므로 3번 기둥을 구하기 위해서 

기둥의 총 번호 합 6(1+2+3)에서 a와 b의 기둥을 제외하면 3번 기둥이 나온다. 

해당 func의 재귀 함수가 모두 끝났다는 것은 n=1인 경우가 나왔다는 뜻이므로 즉, 맨 아래에 있는 원판이 이동가능한 경우라고 말할 수 있다.  

cout << a << ' ' << b

1번 원판은 이미 이동이 끝났으므로 2번 원판을 이동시킨다. 

 

2. n-1개의 원판을 기둥 a에서 b로 옮긴다

void func(6-a-b, b, n-1)

첫번째 기둥에 있는 원판은 모두 이동했으므로 두번째 기둥에 있는 원판을 세번째 기둥으로 이동시킨다. 

 

3. 최소 이동 횟수

원판 k개를 옮기기 위해서 A번의 이동이 필요하다고 가정

k+1 개를 옮기기 위해서 k개의 원판을 빈 곳으로 옮길 때 A번, k+1 원판을 목적지로 옮길 때 1번 

k개의 원판을 다시 빈 곳에서 목적지로 옮길 때 A번이 필요하므로 2A + 1 이동이 필요함

 

예시를 들자면 원판을 1개 옮길때 2 * 0(A) + 1번의 이동이 필요하고 

2개의 원판을 옮길때는 2 * 1(A) + 1 = 3번의 이동이 필요하다. 

즉, 2의 N(원판개수)승 -1 로 나타낼 수 있다.

 

코드

#include<iostream>
using namespace std;

void func(int a, int b, int n) {
    if (n == 1) {
        cout << a << ' ' << b << '\n';
        return;
    }

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


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int k;
    cin >> k;
    int minCnt = 1;
    for (int i = 0; i < k; i++) {
        minCnt = minCnt * 2;
    }
    cout << minCnt - 1 << '\n';

    func(1, 3, k);


    return 0;
}