백준 10826번: 피보나치 수 4

문제 설명

• https://www.acmicpc.net/problem/10826
• 피보나치 숫자를 구하는 문제입니다.

접근법

• memoization기법을 사용해 문제를 풀 수 있습니다.

놓치기 쉬운 부분

1. N이 0일때를 생각해야 합니다.
2. 숫자가 매우 크다는 걸 생각해야 합니다.
   • long으로도 부족합니다.

점화식

$dp[i] = dp[i-1]+dp[i-2]$

정답

import java.util.*;
import java.math.BigInteger;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		BigInteger[] dp = new BigInteger[N+2];
		
		dp[0] = new BigInteger("0");
		dp[1] = new BigInteger("1");
		for (int i = 2; i < dp.length; i++) {
			dp[i] = dp[i-1].add(dp[i-2]);
		}
		System.out.println(dp[N]);
	}
}