하노이 탑 이동 순서 (11729번)
https://www.acmicpc.net/problem/11729
풀이방법
- 재귀로 풀어야 하는 문제로, N번째 원판을 3번째 기둥에 넣기 위해서는 N-1번째 원판을 2번째 기둥에 넣어야하고 2번째 기둥에 있는 원판을 1개만 남겨두고 다시 1번째 기둥에 옮긴 후 1개만 남은 원판을 3번째 기둥에 넣는다.
- 위 과정을 계속 반복하면 된다.
- 재귀 문제는
수학적 귀납법이 제일 중요한데 문제를 직접 디버깅하려고 하면 점점 산으로 가기 때문에 나름대로 공식을 세우고 구현을 해야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
sb.append(pow(2, n) - 1).append('\n');
hanoi(1, 2, 3, n);
System.out.println(sb);
}
private static int pow(int a, int b) {
int n = 0;
int result = 1;
while (n++ != b) {
result *= a;
}
return result;
}
private static void hanoi(int from, int mid, int to, int n) {
if (n == 1) {
sb.append(from).append(' ').append(to).append('\n');
return;
}
hanoi(from, to, mid, n-1);
sb.append(from).append(' ').append(to).append('\n');
hanoi(mid, from, to, n-1);
}
}
Comments powered by Disqus.