[백준 | Java Silver V] (#10826) 피보나치 수 4

문제

https://www.acmicpc.net/problem/10826

---

접근

일반적인 피보나치 방법을 사용하면 틀린다. 입력값이 너무 크게 주어지는 탓이다. (long 자료형으로도 커버되지 않음)

 

BigInteger와 DP를 사용해야 했던 문제!!

 

BigInteger 사용법

BigInteger 선언

보통 문자열을 인자 값으로 넘겨서 선언한다.

            BigInteger[] dp = new BigInteger[10001];
            dp[0] = new BigInteger("0");
            dp[1] = new BigInteger("1");

 

BigInteger 사칙 연산

BigInteger bi1 = new BigInteger("1");
BigInteger bi2 = new BigInteger("2");
		
// 더하기 
bi1.add(bi2));  

//빼기
bi1.subtract(bi2)); 

//곱하기
bi1.multiply(bi2)); 

//나누기
bi1.divide(bi2)); 

//나머지 (모듈러 연산)
bi1.remainder(bi2));

---

첫번째 코드 - 실패

당연히 틀림! 입력값이 너무 커서 이렇게 일반적인 피보나치 방법을 사용하면 안됐다. 

package week9.baek.july7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class S10826 {
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int a = 0, b= 1;
        int t = 0;
        for (int i = 0; i < n - 1; i++) {
            t = a+b;
            a = b;
            b = t;
        }
        System.out.println(t);
    }
}

 

최종 코드 

package week9.baek.july7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class S10826 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        if (n == 0) System.out.println(0);
        else if (n == 1) System.out.println(1);
        else {
            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-2].add(dp[i-1]);
            }
            System.out.print(dp[n]);
        }
    }
}

---

출처

https://propercoding.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%81%B0-%EC%88%AB%EC%9E%90-%EC%A0%95%EC%88%98-BigInteger-%EC%82%AC%EC%9A%A9%EB%B2%95-JAVA-%EC%9E%90%EB%B0%94

[알고리즘] 큰 숫자 (정수) BigInteger 사용법 - JAVA [자바]