문제
N개의 원판을 기둥 1에서 기둥 3으로 옮기는 하노이 탑 문제에서, 최소 이동 횟수를 출력하고 N ≤ 20이면 이동 과정도 출력하라.
입력
첫째 줄에 N (1 ≤ N ≤ 100)이 주어진다.
출력
첫째 줄에 이동 횟수, N ≤ 20이면 이후 줄에 이동 과정(출발 도착)을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 | 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 |
풀이
이동 횟수는 BigInteger로 2^N - 1을 계산하고, N ≤ 20이면 재귀로 이동 과정을 출력한다.
- 이동 횟수 = 2^N - 1. N이 최대 100이므로 BigInteger의
pow()를 사용한다 - N ≤ 20일 때만 재귀 함수로 이동 과정을 출력한다 (2^20 ≈ 100만)
recur(d, st, ed, pr): d개 원판을 st에서 ed로 옮기기- d-1개를 st → pr로 이동, 1개를 st → ed로 이동, d-1개를 pr → ed로 이동
핵심 아이디어: 이동 횟수와 이동 과정을 분리하여 처리한다. 큰 N은 BigInteger로 횟수만 계산하고, 작은 N만 재귀로 과정을 출력하여 시간 초과를 방지한다.
코드
package day449;
import java.io.*;
import java.math.*;
public class Day426BOJ1914하노이의탑 {
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
BigInteger bi = new BigInteger("2");
sb.append(bi.pow(N).subtract(new BigInteger("1")) + "\n");
if (N < 21)
recur(N, 1, 3, 2);
System.out.println(sb);
br.close();
}
public static void recur(int d, int st, int ed, int pr) {
if (d == 1) {
sb.append(st + " " + ed + "\n");
return;
}
recur(d - 1, st, pr, ed);
sb.append(st + " " + ed + "\n");
recur(d - 1, pr, ed, st);
}
}복잡도
- 시간: O(2^N) (N ≤ 20일 때 이동 과정 출력)
- 공간: O(N) (재귀 호출 스택)