백준 11729번 하노이 탑 이동 순서 (C++)

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

11729번: 하노이 탑 이동 순서

 

중학교 수학 문제에 등장했던 하노이의 탑이다.

 

재귀를 이용한다. 5개의 링을 옮기는 과정 속에는 4개의 링을 옮기는 과정이 포함된다.

 

4개의 링을 옮기는 과정 속에는 3개의 링을 옮기는 과정이 포함된다.

 

이런식으로 끄적이며 생각해보면 재귀라는 아이디어를 얻을 수 있을 것이다.

 

예를 들어서, 첫번째 자리에 있던 모든 링들을 세번째 자리로 옮긴다고 하자.

 

이를 위해서는 가장 아래에 깔려있는 가장 큰 링을 빼내야 한다. 이를 위해서는 그것 위에 있는 n - 1 개의 링을 모두 임시적으로 다른 곳에 옮길 필요가 있다.

 

주의할 것은, 2의 20승을 계산할 때, pow함수의 출력이 의도한대로 나오지 않는다는 것이다. 이를 위해서 1 << n 연산을 이용한다.

 

#include<iostream>
#include<math.h>
using namespace std;

void hanoi(int src, int dst, int n) {
	if (n == 1) {
		cout << src << ' ' << dst << '\n';
		return;
	}
	int temp = 6 - src - dst;
	hanoi(src, temp, n - 1); //1 ~ n-1 링을 중간지점에 옮긴다
	cout << src << ' ' << dst << '\n'; //가장 커다란 링을 목적지로 옮긴다.
	hanoi(temp, dst, n - 1); //중간지점에 있던 n - 1 개의 링들을 목적지로 옮긴다.
}

int main(void) {
	int n;
	cin >> n; //옮기는 링의 개수
	//cout << pow(2, n) - 1 << '\n';// 이렇게 쓰면 틀림 n = 20일때 output이 이상해짐
	cout << (1 << n) - 1 << '\n'; // 2의 n승 -1
	hanoi(1, 3, n);

	return 0;
}

 

재귀로 풀이를 진행할 때는

 

1. base condition을 명확히 정의한다.

 

2. 재귀 식을 찾는다.

n개를 옮기려면, n - 1을 다른곳으로 옮긴 이후에 하나 옮기고 다시 n - 1을 목적지로 옮겨야해.. 와 같은

 

이 때, 이전 과정이 올바르게 작동할 것이라는 가정을 하고, 현재의 함수가 올바르게 결과를 내놓을지 판단한다.