백준 g5 11729 하노이 탑 이동 순서 c++

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

11729번: 하노이 탑 이동 순서

 

풀이

이해할 수 있는 가장 쉬운 방법은 최소 가능 횟수로 원판 3, 4, 5개를 플레이해보는 걸 추천한다.

풀다보면 규칙이 보임

 

원판 개수를 n개라고 하고, 원판이 있는 곳을 시작점, 원판을 옮겨야 할 곳을 도착점, 남는 하나를 여분 막대라고 하겠다.

1. 맨 밑 판을 옮기기 위해서 그 위에 있는 n-1개의 판들을 시작점 -> 여분 막대로 옮겨야 한다.

2. 맨 밑 판을 시작점 -> 도착점으로 옮긴다.

3. 여분 막대로 옮겨놨던 n-1개의 판들을 여분 막대 -> 도착점으로 옮긴다.

 

수도 코드

func (원판 개수 n, 시작점, 도착점, 여분) {
	if 원판 개수가 1개
    	출력: 시작점 -> 도착점
	else
    	func(n-1, 시작점, 여분)
        출력: 시작점 -> 도착점 //맨 밑의 판을 도착점으로 옮긴다
        func(n-1, 여분, 도착점)
}

 

 

코드

/*boj g5 11729 하노이 탑 이동 순서*/
#include <iostream>
#include <vector>
#define MAXN 105
using namespace std;

int N;
int K = 0;
vector<pair<int, int>> answer;

void func(int n, int s, int e, int a) {
    if (n == 1) {
        answer.push_back({s, e});
        K++;
    } else {
        func(n - 1, s, a, e);
        answer.push_back({s, e});
        K++;
        func(n - 1, a, e, s);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    func(N, 1, 3, 2);

    cout << K << "\n";
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i].first << " " << answer[i].second << '\n';
    }
}