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

이번 문제는 재귀를 이용한 하노이탑 문제이다.

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

문제에서 요구 하는 것은 2가지이다. 하나는 하노이탑의 최소 이동 횟수, 다른 하나는 하노이탑의 이동 과정.

하노이탑의 최소 이동 횟수를 구하는 것은 어렵지 않다.

결론부터 말하자면, 하노이탑을 옮기는 횟수는 2^n -1이다.

하노이탑을 옮기는 최소 횟수 함수를 F(n)이라고 하면 F(n) = 2F(n-1)+1이다. F(n-1) = 2(F(n-2)+1)이고 F(1) = 1이므로

일반화하면 F(n) = 2^n - 1이 된다.

그럼 이동 과정은 어떻게 구할까?

답은 간단하다. 재귀함수를 작성해서 n-1개를 2번으로 옮긴다음 n번째 판을 3번으로 옮기고, n-1개를 다시 3번으로 옮기는 과정을 표현하면 된다.

코드를 살펴보자.

#include <bits/stdc++.h>
int N;
int a = 1;
int b = 2;
int c = 3;
using namespace std;

void hanoi(int step, int a, int b, int c) {
    if(step==1) {
        cout << a << ' '<< c<<'\n';
        return;
    }
    hanoi(step-1,a,c,b);
    cout << a << ' ' << c << '\n';
    hanoi(step-1,b,a,c);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    cout << pow(2,N)-1<<'\n';
    hanoi(N,a,b,c);
    return 0;
}
// f(n) = f(n-1)+ 1 + f(n-1)

 

• hanoi라는 재귀 함수를 선언하고, 인자로 step, a,b,c를 넘겨준다.
• a,b,c는 각각 1,2,3번 기둥을 뜻한다.
• 좀더 자세히 말해보면 a위치에 들어가는 기둥은 판이 출발하는 기둥, c위치에 들어가는 기둥은 판이 도착하는 기둥, b위치에 들어가는 기둥은 가만히 있는 기둥이다.
• step인자는 현재 단계를 의미한다.
• 재귀함수의 종료 조건은 다음과 같다. step이 1이 되면 1번 기둥에서 3번 기둥으로 옮긴다. (F(1)을 표현한 것이라고 생각하면 편하다.)
• 재귀를 할 부분은 2F(n-1)+1을 표현해 주면 되는데, 주의할 점은 처음 F(n-1)은 2번 기둥으로 옮겨주어야 한다는 것이고 두번째 F(n-1)은 2번 기둥에서 3번 기둥으로 옮겨주어야 한다는 것이다.

이제 제출을 하면

틀리게 된다....!!!

왜 틀렸는지 질문 게시판을 돌아다니다 보니

pow()로 제곱을 해주면 int형으로 형변환을 해주어야 정답 형식과 일치한다고 한다.

#include <bits/stdc++.h>
int N;
int a = 1;
int b = 2;
int c = 3;
using namespace std;

void hanoi(int step, int a, int b, int c) {
    if(step==1) {
        cout << a << ' '<< c<<'\n';
        return;
    }
    hanoi(step-1,a,c,b);
    cout << a << ' ' << c << '\n';
    hanoi(step-1,b,a,c);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    cout << (int)pow(2,N)-1<<'\n';
    hanoi(N,a,b,c);
    return 0;
}
// f(n) = f(n-1)+ 1 + f(n-1)

 

그래서 (int)를 붙여서 형변환까지 해주면 비로소 정답이 된다.