[BOJ][C++] 백준 11729 하노이의 탑 이동순서

하노이의 탑은 설계가 딱!! 들어맞아서 알고나면 참 재밌지만

항상 뚝딱 풀어지지는 않는다...ㅠ 

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

이 분 글을 참고해서 풀었다.

 

탑1, 탑2, 탑3이 있을 때

  - 가장 큰 원판(N)을 제외한 나머지(N-1)을 탑1에서 탑2로 옮긴다. // 이 때 탑3을 활용한다.(거쳐서 옮긴다)

  - 가장 큰 원판(N)을 탑3으로 옮긴다.

  - 나머지(N-1)원판들을 탑3에 다시 옮긴다. // 이 때 탑 1을 활용한다.

요 과정을 반복한다.

 

n==1이 되면(제일 작은 원판의 이동 차례) 그냥 옮겨준다.

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

void Hanoi(int n, int from, int to, int via) {
	if (n == 1) {
		cout << from << " " << to << "\n";
	}
	else {
		Hanoi(n - 1, from, via, to);
		cout << from << " " << to << "\n";
		Hanoi(n - 1, via, to, from);
	}
}

int main()
{
	int N;
	cin >> N;

	cout << (int)pow(2, N) - 1 << "\n";
	Hanoi(N, 1, 3, 2);
}