[백준 11729/c++] 하노이의 탑 이동 순서

재귀문제의 가장 유명한 하노이의 탑 문제이다

하노이의 탑 문제의 핵심은

가장 아래의 원판부터 하나씩 옮겨서 이동해야 한다는 점이다

1. 그러기 위해서는 원판의 총 개수 n 개에서 가장 아래 하나를 뺀 n-1개를 임시위치에 모두 옮겨야 한다

2.  원래 위치에서 가장 아래에 있는 원판을 목표 위치로 이동시킨다

3. 임시 위치에 쌓인 n-1개의 원판을 목표 위치로 이동시킨다

4. 이걸 원판 수 n만큼 반복한다

즉, 위의  알고리즘을 가진다

이동을 출력으로 보여줘야 하므로 원판수 n외에도 원래위치, 임시위치, 목표위치 를 인자로 갖는 함수를 만든다

---

void hanoi(int n인자개수, string from원래위치, string to목표위치, string res임시위치){  // 순서는 정하기 나름

hanoi(n-1)  // n-1 개를 이동해서 임시에 쌓고

옮기기 cnt++  // 가장 아래인 n을 목표 위치로 옮기고

hanoi(n-1)  // 임시에 있는 n-1개를 목표 위치로 옮긴다 // 원래위치 임시위치 목표위치의 인자를 변경하자

}

---

위를 통해 이동을 출력할 수 있다.

이동 개수를 구하기 위해 생각해보면 매 재귀로 쪼개질때마다 한번씩 호출하는 것으로 

한번씩 카운트하면 hanoi(1) 즉 하나를 옮길때마다 카운트하게 할 수 있다

그렇게 출력해보면 원판개수 n과 이동 개수 cnt 와의 관계는 cnt=2^n-1 의 관계를 갖는다재귀에 대해 가장 잘 배울 수 있는 문제였다 어렵다 재귀...

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

11729번: 하노이 탑 이동 순서

#include <bits/stdc++.h>
using namespace std;

void hanoi(int n, string from, string to, string res){
	if(n==0){
		return;
	} else {
		hanoi(n-1, from, res, to);
		cout << from << " " << to << "\n";
		hanoi(n-1, res, to, from);
	}
}

int main(){
	
	int n;
	
	cin >> n;
	
	int cnt=pow(2, n)-1;
	
	cout << cnt << "\n";
	
	hanoi(n, "1", "3", "2");
		
	return 0;
}