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

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

11729번: 하노이 탑 이동 순서

풀이) 

이동횟수는 항상 2^n - 1이 되고, 문제를 크게 3단계로 나누어서 보면 이해가 편하다.

 

1) N - 1개의 원반을 2번째 축으로 옮긴다.

2) 가장 큰 1개의 원반(맨 밑에 있던)을 3번째 축으로 옮긴다.

3) 2번째 축에 있던 N -1개의 원반을 3번째 축으로 옮긴다. 

#include <iostream>
using namespace std;

void disk(int N, int first, int second, int third)
{
    if(N == 1)
        cout << first << " " << third << "\n";
    else
    {
        disk(N - 1, first, third, second);
        cout << first << " " << third << "\n";
        disk(N - 1, second, first, third);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!