99클럽 코테 스터디 21일차 TIL - [프로그래머스] 피보나치 수 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 피보나치 수 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12945

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : n (2 ≤ n ≤ 100,000)
출력 : n번째 피보나치 수 % 1234567

가능한 시간복잡도

O(N)

알고리즘 선택

DP

📌 코드 설계하기

1. n 크기를 가진 배열 fib를 생성한다.
2. 피보나치 수를 구해 배열에 넣는다.
3. n번째 피보나치 수 % 1234567를 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

DP

📌 정답 코드

class Solution {
    public int solution(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;

        for (int i = 2; i <= n; i++) {
            fib[i] = (fib[i - 2] + fib[i - 1]) % 1234567;
        }

        return fib[n]; 
    }
}