https://www.acmicpc.net/problem/11729
1번, 2번, 3번 총 3개의 기둥이 있고 n개의 원판이 있을 경우 원판의 이동 순서는 다음과 같다.
만약, 원판의 개수가 n개일 경우
원판의 개수가 1개일 경우 간단하게 1번 기둥에서 3번 기둥으로 옮기면 끝이다.
import java.io.*;
public class b11729 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
bw.write((int) Math.pow(2, n) - 1 + "\n");
hanoi(n, 1, 2, 3);
bw.flush();
bw.close();
}
public static void hanoi(int n, int start, int middle, int end) throws IOException {
// 이동할 원판의 개수가 1개일 경우
if (n == 1) {
bw.write(start + " " + end + "\n");
return;
}
// 1. n-1개의 원판을 1->2번 기둥으로 이동
hanoi(n - 1, start, end, middle);
// 2. n번째 원판을 1->3번 기둥으로 이동
bw.write(start + " " + end + "\n");
// 3. n-1개의 원판을 2->3번 기둥으로 이동
hanoi(n - 1, middle, start, end);
}
}
재귀의 대표적인 문제인 하노이의 탑. 참 거지같은 문제 중 하나였다. 처음엔 문제조차 이해가 되지 않았는데 계속 보다보니 80 퍼센트 이해했다. 하나씩 따지기 보다는 하나의 덩어리로 생각하면 빛이 보인다. 처음엔 이게 무슨 소리인지 싶겠지만 하다보면 이해할 수 있다!