백준(11729번 하노이 탑 이동 순서)풀이 C++

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

1) 주석 없는 VERSION

#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;

void hanoi(int n, int start, int bypass, int end)
{
    if (n == 1) {
        cout << start << " " << end << '\n';
    }
    else {
        hanoi(n - 1, start, end, bypass);
        cout << start << " " << end << '\n';
        hanoi(n - 1, bypass, start, end);

    }
}
int main() {
    int n;
    cin >> n;

    cout << (1 << n) - 1 << '\n';
    hanoi(n, 1, 2, 3);
    return 0;
}

 

2) 주석 있는 VERSION

 

CASE 1) 원반이 1개인 경우 -> 1번(start)에서 3번(end)으로 바로 이동

 

CASE 2) 원반이 여러 개인 경우

(1) n-1 개의 원판을 3번을 거쳐 2번으로 옮김

(2) 1번의 가장 큰 크기의 원판을 3번으로 옮김

(3) 2번의 n-1개 원판을 1번을 거쳐 3번으로 옮김

 

최솟값 : (2^n)-1 개

 

#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;

void hanoi(int n, int start, int bypass, int end)
{
    //원반이 한개인 경우
    if (n == 1) {
        cout << start << " " << end << '\n';
    }
    else {

        // n-1 개의 원판을 3번(end)를 거쳐 2번(bypass)로 옮김
        hanoi(n - 1, start, end, bypass);

        //1번(start)의 가장 큰 크기의 원판을 3번(end)으로 옮김
        cout << start << " " << end << '\n';

        //2번(bypass)의 n-1개 원판을 1번(start)을 거쳐 3번(end)로 옮김
        hanoi(n - 1, bypass, start, end);

    }
}
int main() {
    int n;
    cin >> n;

    //최솟값은 (2^n)-1 개
    cout << (1 << n) - 1 << '\n';

    //start,bypass,end 호출
    hanoi(n, 1, 2, 3);
    return 0;
}