(C++) - 백준(BOJ) 11729번 : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

분할정복 문제였습니다.

 

풀이방법

 1. 1 -> 2로 n-1개 원판 옮김
 2. 1 -> 3로 남은 한 개(가장 큰 원판) 옮김
 3. 2 -> 3로 n-1개 원판 옮김

이 규칙을 적용하면 됩니다.

 

Code

#include <iostream>
using namespace std;
//n-1개를 2로 옮기고 
//마지막 남은 가장 큰 원판을 3으로 옮긴 뒤
//2에 있는 n-1개의 원판을 3으로 옮겨준다.
int n;
int ans;
int d[21][4];

void a_hanoi(int n, int from, int mid, int to)
{
    int tmp = 0;
    if (n == 1)
    {
        ans++;
    }
    else
    {
        a_hanoi(n - 1, from, to, mid);//n-1개를 두번째로 보낸다.
        ans++;
        a_hanoi(n - 1, mid, from, to);//n-1개를 세번째로 보낸다.
    }
}
void hanoi(int n,int from,int mid,int to) 
{
    int tmp = 0;
    if (n == 1)
    {
        cout << from << ' ' << to << '\n';
    }
    else
    {
        hanoi(n - 1, from, to, mid);//n-1개를 두번째로 보낸다.
        cout << from << ' ' << to << '\n';//마지막 남은 가장 큰 원판을 3으로 옮긴다.
        hanoi(n-1, mid, from, to);//n-1개를 세번째로 보낸다.
    }
}
int main() {
    cin >> n;
    a_hanoi(n, 1, 2, 3);
    cout << ans<<'\n';
    hanoi(n, 1, 2, 3);
}