[ C++ ] #11729 하노이 탑 이동 순서

하노이탑은 재귀로 아주 유명한 문제이다!

이 문제는 아주 복잡하기 때문에 절차지향적으로 하나하나 생각하면 답이 전혀 안나온다...

n개일떄 어떻게 해야하나? 를 생각해야 답이 나온다.

 

hanoi(int a,int b, int n) 이라는 함수는 a에서 b까지 n개의 칸을 옮긴다고 해보자

 

n칸의  탑을 a에서 b까지로 옮긴다면 6-a-b칸을 이용해야한다.

6-a-b칸에 n-1개의 칸을 옮겨놓고 → hanoi(a,6-a-b,n-1)

 맨 밑에 있던 n칸을 b로 옮기고 

6-a-b칸에 있는 n-1개의 탑을 b칸으로 옮기면 된다!  → hanoi(6-a-b,b,n-1)

 

이동한 횟수를 매번 세는 것은 어렵다.

점화식을 이용하여 식을 구해보자!

 

n번째 옮기는 식이 k번이라면 n+1번째는 2*k +1 이 된다.

n개를 옮기고(k) n+1 번째탑을 옮기고(1)  n개를 옮겨야하기 떄문!(k)

 

점화식

#include<iostream>
#include<cmath>

using namespace std;


void hanoi(int a, int b, int n) {  //어디에서 어디로 , 몇개

	if (n == 1) {
		cout << "\n" << a << ' ' << b;
		return;
	}
	hanoi(a, 6 - a - b, n - 1);
	cout << "\n" << a << ' ' << b;
	hanoi(6 - a - b, b, n - 1);

	return;

}

int main() {

	int N;

	cin >> N;

	cout << (1<<N)-1;
	hanoi(1, 3, N);

	return 0;

}