[C++] 하노이의 탑

#include<iostream>
#include<vector>

using namespace std;

void hanoi_three(int n, char start, char to, char via) {
	if (n == 1) {
		cout << "1번 원판을 " << start << "에서 " << to << "에게" << endl;
		return;
	}

	hanoi_three(n - 1, start, via, to);
	cout << n << "번 원판을 " << start << "에서 " << to << "에게" << endl;
	hanoi_three(n - 1, via, to, start);
}

int hanoi_three_num(int n) {
	if (n == 1) {
		return 1;
	}
	return hanoi_three_num(n - 1) + hanoi_three_num(n - 1) + 1;
}

void hanoi_four(int n, char start, char to, char via1, char via2) {
	if (n == 0) {
		return;
	}
	if (n == 1) {
		cout << "1번 원판을 " << start << "에서 " << to << "에게" << endl;
		return;
	}

	hanoi_four(n - 2, start, via1, to, via2);
	cout << n - 1 << "번 원판을 " << start << "에서 " << via2 << "에게" << endl;
	cout << n << "번 원판을 " << start << "에서 " << to << "에게" << endl;
	cout << n - 1 << "번 원판을 " << via2 << "에서 " << to << "에게" << endl;
	hanoi_four(n - 2, via1, to, start, via2);
}


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

	//hanoi_three(N, 'A', 'C', 'B');
	//cout << hanoi_three_num(N) << endl;
	hanoi_four(N, 'A', 'D', 'B', 'C');

	return 0;
}

하노이의 탑 기둥 4개는 생각보다 많이 복잡
3개는 점화식, 최소 이동횟수, 경로 구하는 법 둘다 알아놓고
4개는 최소 이동횟수만 이해하기

테스트 케이스의 수를 정하지 않고 계속 받을경우
while(cin>>n) 형태로 만들면 EOF 값을 리턴하여 종료

 

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