c++ 백준 11729번 문제

백준 11729 하노이탑 문제

이동횟수

pow(2,n) -1;

점화식

Dp[n]= Dp[n-1]*2-1;

규칙

1. (n-1)개의 판을 mid로 옮김
   1-1

2. from에 있는 n을 to로 옮김.
3. mid에 있는 (n-1)개의 판을 from으로 (n-2)개 옮김
4. 재귀

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

void Hanoi(int N, int A, int B, int C)
{
	if (N == 1)
		cout << A << " " << C << '\n';
	else
	{
		Hanoi(N - 1, A, C, B);
		cout << A << " " << C << '\n';
		Hanoi(N - 1, B, A, C);
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	int k = (int)pow(2, N) - 1;
	cout << k << '\n';
	Hanoi(N, 1, 2, 3);

	return 0;
}

다시 한번 풀어보기