[프로그래머스] 피보나치 수 (JAVA)

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 피보나치 수

---

[풀이]

1. 100001의 크기인 dp 배열을 생성해준다.

2. dp배열의 0번지와 1번지를 각각 0, 1을 넣어준다.

3. dp[i]에 dp[i-1] + dp[i-2]를 넣어준다.

4. 해당 값을 1234567로 나눠 나머지를 넣어준다.

5. 3. ~ 4.를 n까지 반복한다.

6. n에 해당하는 값을 출력한다.

[접근]

1. 피보나치라는 것을 보자마자 dp로 풀면 되겠다고 생각하였다.

[코드]

class Solution {
    public int solution(int n) {
        int[] dp = new int[100001];
        
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= 1234567;
        }
        
        return dp[n];
    }
}