DP 로 피보나치 수 구하기

백준 2748번을 DP를 이용해 Java로 풀어봤다.
역시 이번에도 알고리즘 공부 시작한 지 얼마 안 된 티가 나는 실수를 해서 삽질을 짧게나마 했다...^^

문제 조건대로면 90번째 피보나치수까지 커버를 해야 하는데, int형으로 받아서 계속 틀렸던 거다. 실제로 90번째 피보나치수를 구해보니 int 범위를 한참 벗어난다... long으로 바꿔주자마자 해결이 됐다.

아직 갈 길이 멀구나~...

짧게 요점만 적으면, 이미 계산했던 전력이 있는 놈을 다시 계산해주지 않는 것이 핵심이고 이를 위해서 배열을 사용한다.

아래는 내가 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj2748 {
    static int n;
    static long[] dp = new long[91];

    static long fib(int n){
        if(dp[n]==-1)
            dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bfr.readLine());
        for(int i=0; i<91; i++)
            dp[i] = -1;
        dp[0] = 0; dp[1] = 1;
        System.out.println(fib(n));
    }
}

개빡친다...^^

오늘 배운 것

결괏값의 범위를 반드시 생각하고 변수의 type을 정하자!