백준 - 11729 하노이의 탑

재귀 너무 어렵다.. Dp 함수 자체를 이해하는 과정과 n==1 일 때 이해가 어려웠다.

 

n == 1 일 때는 마지막 하나남은 가장 작은 원판이 to 로 도착함을 의미한다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int answer = 1;

void Dp(int n , int from, int by, int to)
{
	if (n == 1)
	{
		cout << from << " " << to << "\n";
		return;
	}

	Dp(n - 1, from, to, by);
	cout << from << " " << to << "\n";
	Dp(n - 1, by, from, to);

}

int main(void)
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	int n;
	cin >> n;

	int from = 1;
	int by = 2;
	int target = 3;

	

	for (int i = 1; i <= n; ++i)
	{
		answer *= 2;
	}

	cout << answer - 1 << endl;

	Dp(n, from, by, target);



	return 0;
}