[백준 11729] 하노이 탑 이동 순서 (C/C++)

Problem

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

11729번: 하노이 탑 이동 순서

 

Comment

이 문제의 핵심은 두 가지입니다.

• 재귀 함수를 이용해 하노이의 탑 계산의 조건에 맞게 적절한 값 도출
• 원판 이동 횟수 계산

 

이 문제에서는 아래의 조건에 맞게 원판을 옮겨야 합니다.

• 한 번에 하나의 원판만 옮길 수 있음
• 맨 위에 있는 원판만 옮길 수 있음
• 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음
• 중간의 막대를 임시적으로 이용할 수 있으나 위의 조건들을 지켜야 함

 

원판을 from에서 via를 거쳐 to까지 옮긴다고 해봅시다.

1. $n$개의 원판이 from에 쌓여있습니다. 먼저, 위에 쌓여있는 $n - 1$개의 원판을 via로 옮깁니다.
2. 그럼 from에 제일 밑에 있던 1개의 원판이 남을겁니다. 이 원판을 to로 옮깁니다.
3. via에 있는 $n - 1$개의 원판을 to로 옮깁니다.

 

이 과정에서 원판의 횟수를 짐작해볼 수 있습니다. $n - 1$개의 원판을 옮기고, 1개의 원판을 옮기고, $n - 1$개의 원판을 옮긴다고 써져있습니다. 따라서 한 번 사이클이 돌 때마다 $2 * n + 1$개의 원판을 옮기는 것을 알 수 있습니다.

 

이 점들을 고려하여 코드를 작성하면 아래와 같습니다.

 

Code

#include <stdio.h>

void hanoi(int from, int via, int to, int n) {
	if (n == 1) {
		printf("%d %d\n", from, to);
	} else {
		hanoi(from, to, via, n - 1);
		printf("%d %d\n", from, to);
		hanoi(via, from, to, n - 1);
	}
}

void hanoi_cnt(int n) {
	int num = 1;
	while (--n) {
		num = num * 2 + 1;
	}
	printf("%d\n", num);
}

int main() {
	int n;
	scanf("%d", &n);
	hanoi_cnt(n);
	hanoi(1, 2, 3, n);
}

 

Result