백준 11729 하노이 탑 이동 순서

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

서론

재귀가 있는건 알겠는데 정확하게 보이질 않아서 위키를 참고했다.

참고 : https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

풀이과정

하노이의 탑 게임을 하면서 n이 1부터 4까지의 답을 적어보았다.

n이 2일때의 답이 n이 4일때의 최하단과 동일한게 보이긴 하는데 다른 별다른 규칙성이 보이질 않는다.

그런데 게임을 하다보니

n이 3일때의 게임 진행 도중 n이 2일때를 만날 수 있음을 확인했다.

왼쪽 기둥을 시, 중간 기둥을 빈, 오른쪽기둥을 목이라고 하고(시작, 빈곳, 목표)

게임 도중 발견한 규칙을 생각하며 표1의 숫자들을 한글로 바꾼 후 위치를 구분시켜 적었는데 재귀적 특성이 나타난다.

그런데 틀만 보이고 내용물은 제멋대로다.

표 2에서 n이 3일때 위와 같은 상황이 되었을때, 중간기둥은 빈으로 표시했으나 표3에서는 시로 표시했다.

n이 2일때의 새로운 시작이다.

즉 표2에서는 빈->목이였으나 표3에서는 시->목이다.

이렇게 하면 틀 뿐만 아니라 내용까지 재귀적특성이 나타난다.

더불어 구분을 간결하게 하면 재귀적 특성이 더 잘 보인다.

구현

pow의 출력결과는 double이라 int로 바꿔주지 않으면 틀렸다고 나온다.

//c++

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

void tower(int n, int start, int empty, int end) {
	if (n == 1) { 
		printf("%d %d\n", start, end);
		return;
	}

	tower(n - 1, start, end, empty);
	tower(1, start, empty, end);
	tower(n - 1, empty, start, end);

	return;
}

int main() {
	int n;
	cin >> n;
	cout << (int)pow(2, n) - 1 << endl;
	tower(n, 1, 2, 3);
}