baekjoon 11729

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

---

Idea

1번 기둥을 출발 2번 기둥을 보조 3번 기둥을 도착 기둥이라고 생각하자.
그럼 하노이 탑 함수의 코드는 다음과 같다

void hanoi(int N, int from, int to, int sub);

N이 3인 경우를 예시로 생각해보자. 원판은 총 3개이고 출발 기둥에서 도착 기둥까지 규칙을 지키며 옮겨야 한다. 3개의 원판 중 제일 작은 원판을 제외하고 아무것도 없다 생각하고 1 원판을 도착 기둥으로 옮긴다.
그럼 3번 기둥위로 두 번째 작은 원판을 올리면 규칙에 어긋나기 때문에 2번 기둥으로 옮길 수 밖에 없다. 그러므로 출발 기둥 보조 기둥 도착 기둥의 역할이 바뀌게 된다. N을 1만큼 감소하고 하노이 탑 함수를 다시 호출한다.

역할이 바뀌는 순간을 잘 생각하고 기둥 밑에 깔려있는 원판을 배제하는 것이 중요하다고 생각한다. 그림판으로 몇 번 그려보니 함수가 완성되었다.

void hanoi(int N, int from, int to, int sub) {
	if (N == 1) {
		printf("%d %d\n", from, to);
		return;
	}

	hanoi(N - 1, from, sub, to);
	printf("%d %d\n", from, to);
	hanoi(N - 1, sub, to, from);
}

또 문제에서는 반복 횟수 K를 출력해야 하는데 printf 를 할 때마다 K 변수를 1 만큼 증가시키고 하노이 탑 함수를 빠져 나와 출력하면 되는 간단한 문제처럼 보이지만 이동 과정을 출력하기 전 K를 출력해야 한다. 규칙을 발견하면 이것 또한 쉬운데 공식을 유도해낸 건 아니고 몇 가지 연산을 끄적이다 보니 공식을 찾았다.

2^N - 1

int cnt = pow(2, N) - 1;

---

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

void hanoi(int N, int from, int to, int sub);

int main(void) {
	int N;

	scanf("%d", &N);
	
	int cnt = pow(2, N) - 1;
	printf("%d\n", cnt);
	hanoi(N, 1, 3, 2);

	return 0;
}

void hanoi(int N, int from, int to, int sub) {
	if (N == 1) {
		printf("%d %d\n", from, to);
		return;
	}

	hanoi(N - 1, from, sub, to);
	printf("%d %d\n", from, to);
	hanoi(N - 1, sub, to, from);
}