20 삐약 : 백준 11729 [C++]

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

11729번: 하노이 탑 이동 순서

 

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

void hanoi(int n, int start, int mid, int dest) {
	if (n == 1)  printf("%d %d\n", start, dest);
	else {
		hanoi(n - 1, start, dest,mid);
		printf("%d %d\n", start, dest);
		hanoi(n - 1, mid, start, dest);
	}
}
int main() {
	int num;
	cin >> num;
	// cout << (int)pow(2, num) - 1 << '\n';
	cout << (1 << num) - 1 << '\n';
	hanoi(num, 1, 2, 3);

 

hanoi(N) : N개의 원반을 옮긴다

hanoi(N-1) : n-1개의 원반을 옮긴다.

 

*재귀 가능성 여부 판단 : hanoi(3)에서 hanoi(2)를 발견할 수 있는가?

  => 발견 가능!! => 재귀로 구현 가능

hanoi(N)은 두번의 hanoi(N-1)의 재귀 과정을 요구

 

 => 전체 과정을 세 과정의 연속을 로 분해 가능

 

1. hanoi(n-1) : n-1개의 원반을 2번으로 이동

2. 1번에 있는 가장 큰 원반을 3번으로 이동

3. hanoi(n-1) : 2번에 있는 n-1개의 원반을 3으로 이동

 

 

 

 

참고 : https://shoark7.github.io/programming/algorithm/tower-of-hanoi