[백준/boj] 10826: 피보나치 수4 (Java) / BigInteger / DP

문제

10826번: 피보나치 수 4

풀이

import java.io.*;
import java.math.*;

public class Main_BOJ_10826_피보나치수4 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BigInteger[] dp;
	
	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(br.readLine());
		dp = new BigInteger[n+1];
		if(n == 0 || n == 1) {
			System.out.println(n);
			return;
		}
		dp[0]=BigInteger.ZERO; // *
		dp[1]=BigInteger.ONE;
		dp[2]=BigInteger.ONE;
		for(int i=3; i<=n; i++) {
			dp[i] = dp[i-1].add(dp[i-2]); // *
		}
		System.out.println(dp[n]);
	}
}

• 이 문제의 경우 들어올 수 있는 수가 10,000까지 이기 때문에 일반 재귀로 풀어도 시간 초과가 나고, int / long의 범위도 넘어간다.
• 이때 사용할 수 있는게 BigInteger 이다. // * 에서 볼 수 있듯이 사용법이 좀 특이하다. String형식으로 사용되기 때문이다. 더 자세한 사용법은 아래 블로그에 나와 있다.
• https://coding-factory.tistory.com/604
• dp 를 이용해 dp[n]까지 반복문을 돌린 후 dp[n]을 사용한다. 이 방법 같은 경우는 테스트 케이스가 여러개일 수록 더 좋다!