백준 10826: 피보나치 수 4[JAVA]

[문제 링크]

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

[난이도]

- Silver 5

 

[알고리즘]

- DP

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int n = Integer.parseInt(br.readLine());


        if (n == 0) {
            bw.write("0");
        } else {
            BigInteger[] dp = new BigInteger[n + 1];

            dp[0] = BigInteger.ZERO;
            dp[1] = BigInteger.ONE;

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

            bw.write(dp[n].toString());
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

[풀이]

bottom-up 방식

1. 문제 이해

1. n 번째 피보나치 수 찾기

2. dp 배열 정의

dp[0] = 0

dp[1] = 1

dp[2] = 1

dp[3] = 2

dp[4] = 3

dp[5] = 5

3. 초기값 설정

dp[0] = 0

dp[1] = 1

4. 점화식 작성

dp[n] = dp[n-2] + dp[n-1]

 

if문으로 n이 0일때 조건문으로 둔 이유 : 초기값을 설정하는 과정에서 dp[1]을 초기화하기때문에

n이 0일경우 dp[1]에 접근할 수 없어서 런타임에러(ArrayIndexOutOfBounds)가 발생한다.