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

11729번: 하노이 탑 이동 순서

기둥이 A, B, C이고 N이 2개일 때부터 4개일 때까지 순서를 적어나가보면

B에 N-1개의 원반을 쌓아놓은 후 C에 다 옮기는 방식이 공통적으로 나온다. 즉,

​

1. A -> B 로 N-1개 옮김

2. A -> C 로 1개 옮김 (가장 큰 원반)

3. B -> C 로 N-1개 옮김

​

이렇게 세 번의 과정으로 나눌 수 있다.

이걸 그대로 재귀함수에 갖다 넣으면 해결된다.

#include <iostream>
#include <cmath>
using namespace std;

void TowerOfHanoi(int from, int middle, int to, int N) {
	if (N != 0) {
		TowerOfHanoi(from, to, middle, N - 1);
		cout << from << " " << to << "\n";
		TowerOfHanoi(middle, from, to, N - 1);
	}
}

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

 

 

이 분 설명이 제일 쉽게 잘 되어 있다.

​

솔직히 이리저리 규칙을 찾고 조건문으로 해결하려고 애쓰다가 하노이 탑의 규칙을 구글링해서 그 규칙대로 그냥 단순하게 함수에 넣어봤는데 답이 나와서 당황했다.

재귀 문제에 익숙해질 때까지 많이 풀어봐야 할 것 같다.

​