1914번: 하노이 탑
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
boj 11729 하노이 탑 이동 순서
www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이
emoney96.tistory.com
이 문제랑 같은 문제입니다.
이동 순서는 위의 문제와 동일하게 해주시면 됩니다.
하나 다른점은 N이 최대 100이며, N>20인 경우에는 횟수만 출력합니다.
2^100 - 1 = 1267650600228229401496703205375 이므로 long의 범위도 초과합니다.
그래서 자바의 BigInteger를 사용합니다.
BigInteger에 pow라는 지수메소드가 있어서 2^N을 구할 수 있고, subtract 메소드로 1을 감소시켜줍니다.
|
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
38
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
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 BigInteger ans = new BigInteger("2");
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());
ans = ans.pow(N).subtract(new BigInteger("1"));
}
public static void main(String[] args) throws Exception {
input();
System.out.println(ans);
if (N > 20) {
return;
}
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 11729 하노이 탑 이동 순서 (0) | 2021.02.07 |
| boj 1244 스위치 켜고 끄기 (0) | 2021.02.01 |
| boj 20127 Y-수열 (0) | 2021.01.22 |