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

0

백준

목록 보기
204/271
post-thumbnail

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

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

vector<pair<int, int>> moves;

void hanoi(int plates, int start, int mid, int end) {
	if (plates == 1) {
		moves.push_back({ start, end });
		return;
	}

	//n-1개의 원판 1 -> 2
	hanoi(plates - 1, start, end, mid);
	//맨 아래 원판 1 -> 3
	hanoi(1, start, mid, end);
	//n-1개의 원판 2 -> 3
	hanoi(plates - 1, mid, start, end);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n;

	//n개의 원판 1 -> 3
	hanoi(n, 1, 2, 3);

	cout << moves.size() << "\n";
	for (int i = 0; i < moves.size(); ++i) {
		cout << moves[i].first << " " << moves[i].second << "\n";
	}
	return 0;
}
profile
Be able to be vulnerable, in search of truth

0개의 댓글