[백준] 2748 피보나치 수2 (자바) : DP [브론즈2]

✔️ 문제 설명 (펼치기)

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

예제 입력 1 

10

예제 출력 1 

55

 

 

✔️ 문제 풀이

이 문제의 경우 이전에 풀었던 문제보다 단순하고 난이도 낮은 문제이다.

우선 문제에서 피보나치 점화식 Fn = Fn-1 + Fn-2 (n ≥ 2)을 제시하였다. 

 

• dp 는 Fn 값을 저장을 하기 위한 배열이다.
• n은 90보다 작거나 같은 자연수 이므로, 배열 dp의 크기는 91로 설정한다. 
• 배열 dp는 수의 범위를 고려하여 long 형으로 지정한다. 
• dp[0] = 0, dp[1] = 1 로 고정

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

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

        long[] dp = new long[91];

        dp[0] = 0;
        dp[1] = 1;
        for(int i =2; i<=n; i++){
            dp[i] = dp[i-2] + dp[i-1];
        }

        System.out.println(dp[n]);

    }
}

 

✔️ [마주한 오류]

아무리 봐도 푼 알고리즘에 문제가 없었으나 오답이 떴다.

이럴 때는 자료구조에 문제가 있나 생각해볼 필요가 있다. 

n = 17인 경우, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 즉, 피보나치 수가 1597이된다. 

만약에 n이 90인 경우에는 기하급수 적으로 수가 늘어나 int 범위를 넘어가게 될것이다. 

따라서 int 배열을 long 배열로 바꿔주었다. !