[C언어 / 백준 - 1914번] 하노이 탑 (재귀)

www.acmicpc.net/problem/1914

1914번: 하노이 탑

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

 

 

이 문제의 핵심은 재귀를 이용한 하노이 탑도 있지만 변수 선언을 통해 해결할 수 없는 정수처리이다. 

이 부분은 biginter함수를 이용하여 unsigned long long보다 큰 변수를 다루도록 한다

 

하노이의 탑 관련 문제해결은

바킹독 알고리즘 - <재귀>를 통해 배울 수 있다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int n;
// Big integer
// 정수형으로 나타낼 수 있는 최대크기보다 더 큰 수를 나타내고자 할 때 사용하는 방법으로 문자열을 이용하여야한다.
void Power(int x, int n, char arr[]) {
	// x의 n승을 arr이라는 문자열 배열에 저장하고자 한다
	int temp = 0, last = 0, cnt = 0;
	arr[0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= last; j++) {
			temp = arr[j] * x;
			if (temp >= 10) {
				arr[j] = temp % 10 + cnt;
				cnt = temp / 10;

				if (j == last) {
					arr[++last] = cnt;
					cnt = 0;
					break;
				}
			}
			else {
				arr[j] = temp + cnt;
				cnt = 0;
			}
		}
	}
	arr[0] -= 1;
	for (int i = last; i >= 0; i--) printf("%d", arr[i]);
	printf("\n");
}

void func(int n, int a, int b) {
	if (n == 1) {
		printf("%d %d\n", a, b);
		return;
	}

	func(n - 1, a, 6 - a- b);
	printf("%d %d\n", a, b);
	func(n - 1, 6 - a - b, b);
}

int main() {
	char result[35];

	scanf("%d", &n);
	Power(2, n, result);

	if (n > 20) return 0;
	func(n, 1, 3);

	return 0;
}

-> www.youtube.com/watch?v=8vDDJm5EewM&t=1484s