[12945] 피보나치 수

✔ 피보나치 수

[프로그래머스 12945]

문제 분석하기

동적 계획법을 통해 피보나치 수를 구해 저장한 후 사용하도록 함

손으로 풀어보기

1. 동적 계획법을 통해 피보나치 수를 구해 반환
   • F(n) = F(n - 2) + (n - 1)

슈도코드 작성하기

n(2 이상의 자연수)
answer(n번째 피보나치 수를 1234567으로 나눈 나머지 값)
D(피보나치 수를 저장할 DP 테이블)
D[0] = 0
D[1] = 1
for(i -> 2부터 n까지) {
    D[i] = (D[i - 1] + D[i - 2]) % 1234567
}
answer = D[n]
answer 반환

코드 구현하기

/**
 * 12945) 피보나치_수
 */
public class L017_12945 {
    // n(2 이상의 자연수)
    public int solution(int n) {
        // answer(n번째 피보나치 수를 1234567으로 나눈 나머지 값)
        int answer = 0;
        // D(피보나치 수를 저장할 DP 테이블)
        int[] D = new int[n + 1];
        // 이미 아는 가장 작은 문제를 저장
        D[0] = 0;
        D[1] = 1;
        // 구한 값을 D 테이블에 저장
        for (int i = 2; i <= n; i++) {
            // 오버플로우를 방지하기 위해 미리 1234567으로 나눈 나머지 값을 저장
            D[i] = (D[i - 1] + D[i - 2]) % 1234567;
        }
        // answer애 n의 피보나치 수를 저장
        answer = D[n];
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L017_12945 solution = new L017_12945();

        int n = 3;

        int result = solution.solution(n);

        System.out.println(result);
    }
}