문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
풀이
수학 얘기를 할 게 아니기 때문에, 수학 내용의 점화식을 구한다거나 뭐하거나.. 내용은 다루지 않겠다. 말 그대로 n 개의 원판을 모두 옮기기 위해서는 최소 2^n -1 번을 이동해야한다.
재귀 방식으로 해결할 것이고, n 번째 상황에 대해 어떤 동작을 해야할지 고민해보자.
1. n 번째 원판을 세 번째 장대로 옮기기 위해서는 n -1 번째까지의 원판을 모두 두 번째 장대로 옮긴다.
2. n 번째 원판을 세 번째 장대로 옮긴다.
3. 두 번째 있던 n - 1개의 원판을 세 번째 장대로 옮긴다.
위의 단계에서는 첫 번째 장대가 시작, 두 번째 장대가 경유, 세 번째 장대가 도착이다.
즉, 재귀 점화식은 완전히 일반화 시켜서 작성하고, 처음 시작할 때 출발, 경유, 도착을 정해주기만 하면 계속해서 재귀를 돌면서 필요에 따라 출발 경유 도착을 바꾸어 가면서 재귀를 돌게 된다.
import java.io.*;
public class Main {
static int n;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
sb.append((1 << n) - 1).append("\n");
hanoi(n, 1, 2, 3);
System.out.println(sb);
}
static void hanoi(int n, int from, int by, int to) {
// 원판이 없으면 종료
if (n == 0) {
return;
}
// n - 1개 원판을 from 에서 by 로 이동
hanoi(n - 1, from, to, by);
// n 번째 원판을 from 에서 to 로 이동
sb.append(from).append(" ").append(to).append("\n");
// by 에 있는 n - 1개 원판을 to 로 이동
hanoi(n - 1, by, from, to);
}
}사실 재귀는 항상 어렵게 느껴지긴한다. 풀이를 한 3번 정도 기억 안날 시점에 지웠다가 다시 작성해보면서 좀 익혔던 거 같다.
시간 복잡도는 최소 이동 횟수가 2^n - 1 이므로 O(2^n)이 될 것 이다.
