algorithm/Implementation
boj 1914 하노이 탑
와이에쓰
2021. 2. 7. 13:09
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 |