큰수에 해당하는 글 1

백준 알고리즘 4150번 피보나치 수 문제

JAVA/알고리즘|2018. 8. 1. 22:16


저번에 공부한 BigInteger를 응용하여 알고리즘 문제를 풀어보자.

이번문제는 피포나치 수열을 해결하는 문제이다. 저번에 포스팅 했었던 피보나치 수열을 구하는 방법은 재귀와 DP 그리고 반복문이 있다.

이번 문제는 반복문을 사용하여 구해보자. 위에 문제를 보면 데이터의 결과 크기가 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
32
33
34
35
36
37
38
39
40
41
package test;
 
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Fibanachi {
    
    
    public static void main(String args[]) {
        
        List<BigInteger> data = new ArrayList<>();
 
        data.add(BigInteger.ZERO);
        data.add(BigInteger.ONE);
 
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
 
        if (0 == num) {
            System.out.println(data.get(0));
            in.close();
            return;
        }
 
        if (1 == num) {
            System.out.println(data.get(1));
            in.close();
            return;
        }
 
        for (int i = 2; i <= num; i++) {
            data.add(i, data.get(i - 1).add(data.get(i - 2)));
        }
 
        System.out.println(data.get(num));
        in.close();
    }
 
}
cs


자세한 코드는 아래 URL을 통해서 확인가능하다.
https://github.com/weduls/algorithm/tree/master/%EC%88%98%ED%95%99/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98

댓글()