11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이탑 이동 횟수와 순서를 출력하는 문제입니다.
하노이탑은 3개의 기둥이 있고, 한 기둥에 원판들이 작은 것이 위에 있고 순서대로 밑으로 쌓여있습니다.
한 번에 하나의 원판만 옮길 수 있고, 큰 원판이 작은 원판 위에 있으면 안됩니다.
일단 원판이 n개 일 때, 이동 횟수는 2^n - 1개입니다.
비트연산을 이용하면 빠르게 구할 수 있습니다.
그리고, 재귀를 통해 순서를 출력해주시면 됩니다.
저는 "func(n, a, b, c) : n개의 원판이 a에서 c로 이동하는 경우" 이렇게 함수를 선언하였습니다.
그 다음 n - 1개를 a에서 b로 옮기고, 나머지 1개를 a에서 c로 옮기고, n - 1개를 b에서 c를 옮기는 로직입니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int N;
static void func(int n, int a, int b, int c) {
if (n < 1)
return;
func(n - 1, a, c, b);
sb.append(a + " " + c + "\n");
func(n - 1, b, a, c);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
sb.append((2 << (N - 1)) - 1 + "\n");
}
public static void main(String[] args) throws Exception {
input();
func(N, 1, 2, 3);
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 16918 봄버맨 (0) | 2021.02.17 |
|---|---|
| boj 16935 배열 돌리기 3 (0) | 2021.02.10 |
| boj 1914 하노이 탑 (0) | 2021.02.07 |
| boj 1244 스위치 켜고 끄기 (0) | 2021.02.01 |
| boj 20127 Y-수열 (0) | 2021.01.22 |