www.acmicpc.net/problem/10826

 

10826번: 피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

 

점화식 : dp[i] = dp[i - 1] + dp[i - 2]

앞의 두 개의 수를 더한 값이 자신의 값이 됩니다.

 

이 문제는 N이 10000까지 오기때문에 long의 범위를 초과합니다.

자바에는 BigInteger라는 클래스가 있기때문에 이용 사용하여 쉽게 구할 수 있습니다.

 

 

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.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
 
    static void solve() {
        BigInteger dp[] = new BigInteger[10001];
        dp[0= new BigInteger("0");
        dp[1= new BigInteger("1");
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
        }
 
        System.out.println(dp[N]);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}
cs

'algorithm > dp' 카테고리의 다른 글

boj 1912 연속합  (0) 2021.02.18
boj 10211 Maximum Subarray  (0) 2021.02.18
boj 5569 출근 경로  (0) 2021.02.06
boj 1010 다리 놓기  (0) 2021.02.05
boj 5557 1학년  (0) 2021.02.05

www.acmicpc.net/problem/1914

 

1914번: 하노이 탑

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

emoney96.tistory.com/102

 

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, 123);
        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

www.acmicpc.net/problem/1837

 

1837번: 암호제작

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로

www.acmicpc.net

BigInteger를 사용하는 문제입니다.

P는 소수의 곱으로 이루어져있지만 10^100이라는 수가 입력으로 주어집니다.

K는 P가 좋은 암호인지, 좋지 않은 암호인지 구별하는 수이며 1000000까지 주어집니다.

 

P를 나타내는 소수 p, q 중에 하나라도 K보다 작으면 이 암호P는 좋지 않은 암호입니다.

하지만 P가 너무 큰 수이기 때문에 소수를 직접 구할 수 없으므로 K범위 내의 소수를 모두 구하여

 

구한 소수들 중 P와 나머지 연산을 해서 0이 되는 수가 있으면 BAD, 없으면 GOOD를 출력하였습니다.

 

 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static BigInteger P, K;
    static boolean sosuchk[] = new boolean[1000001];
    static Set<BigInteger> sosu = new TreeSet<>();
    static int k;
 
    static void func() {
        Iterator<BigInteger> iter = sosu.iterator();
        while (iter.hasNext()) {
            BigInteger a = iter.next();
            if (a.compareTo(K) >= 0)
                break;
 
            if (P.mod(a).equals(new BigInteger("0"))) {
                System.out.println("BAD " + a);
                return;
            }
        }
 
        System.out.println("GOOD");
    }
 
    static void init() {
        for (int i = 2; i <= 1000000; i++) {
            if (sosuchk[i])
                continue;
 
            sosu.add(new BigInteger(Integer.toString(i)));
            for (int j = 2; i * j <= 1000000; j++) {
                if (sosuchk[i * j])
                    continue;
 
                sosuchk[i * j] = true;
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        P = new BigInteger(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        K = new BigInteger(Integer.toString(k));
    }
 
    public static void main(String[] args) throws Exception {
        init();
        input();
        func();
    }
}
cs

'algorithm > Math' 카테고리의 다른 글

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 15740 A+B - 9  (0) 2021.01.31
boj 1002 터렛  (0) 2021.01.27

www.acmicpc.net/problem/15740

 

15740번: A+B - 9

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

자바 공부하다가 BigInteger라는 객체가 있는걸 알았습니다..

존재를 까먹기 전에 포스팅이라도 하려고 급하게 문제를 풀었습니다..

 

이 문제는 A+B를 출력하는 매우 간단한 문제이지만 입력으로 주어지는 수가 -10^10000 ~ 10^10000이라서

int, long으로는 해결할 수 없습니다. 그래서 BigInteger를 사용해야 합니다.

BigInteger는 일반적인 +, -와 같은 연산은 불가능하며,

add(덧셈), subtract(뺄셈), multiply(곱셈), divide(나눗셈), remainder(나머지)와 같은 내부 메소드를 사용해야합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 BigInteger A, B;
    
    static void input() throws Exception{
        st = new StringTokenizer(br.readLine());
        
        A = new BigInteger(st.nextToken());
        B = new BigInteger(st.nextToken());
    }
    
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(A.add(B));
    }
}
cs

 

 

 

 

 

그리고... 파이썬 코드입니다.

1
2
3
4
x, y = input().split()
= int(x)
= int(y)
print(x + y)
cs

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

너무 간단한데요;;

 

C++로 BigInteger를 직접 구현했던 때가 기억이 납니다 ㅎㅎ;;

 

'algorithm > Math' 카테고리의 다른 글

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 1837 암호제작  (0) 2021.02.04
boj 1002 터렛  (0) 2021.01.27

+ Recent posts