프로그래머스 피보나치 수 JAVA 풀이 (DP, 공간 최적화)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

피보나치 수열은 다음과 같은 규칙을 가진다.

n번째 피보나치 수를 구한 뒤, 1234567로 나눈 나머지를 반환하는 문제이다.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

---

📌 접근 방법

처음에는 DP 배열을 사용하여 모든 피보나치 값을 저장할 수 있다.

arr[i] = arr[i - 1] + arr[i - 2];

하지만 현재 값을 계산할 때 필요한 것은 직전 두 개의 값뿐이다.

따라서 배열 대신 두 개의 변수만 사용하여 공간을 절약할 수 있다.

또한 피보나치 수는 매우 빠르게 증가하므로 매 계산마다 1234567로 나눈 나머지를 저장한다.

---

📌 핵심 아이디어

1. 이전 두 값만 저장

피보나치 수열은 직전 두 값만 필요하므로 배열을 사용할 필요가 없다.

int prev2 = 0;
int prev1 = 1;

---

2. 다음 피보나치 수 계산

현재 값을 계산하면서 동시에 나머지 연산을 수행한다.

answer = (prev1 + prev2) % 1234567;

---

3. 값 이동

다음 계산을 위해 이전 값들을 한 칸씩 이동시킨다.

prev2 = prev1;
prev1 = answer;

예시

0, 1 → 1
1, 1 → 2
1, 2 → 3
2, 3 → 5

---

4. 나머지 연산을 미리 수행하는 이유

피보나치 수는 매우 빠르게 증가한다.

따라서 큰 n에서는 자료형 범위를 초과할 수 있다.

모듈러 연산의 성질을 이용하면

F(50) = 12,586,269,025

이므로 매 단계마다 나머지 연산을 수행해도 최종 결과는 동일하다.

(a + b) % M
=
((a % M) + (b % M)) % M

---

📌 전체 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int prev2 = 0;
        int prev1 = 1;

        for (int i = 2; i <= n; i++) {
            answer = (prev1 + prev2) % 1234567;
            prev2 = prev1;
            prev1 = answer;
        }

        return answer;
    }
}

 

---

📄 정리

• 피보나치 수열은 이전 두 값만으로 계산할 수 있다.
• 배열 대신 변수 두 개를 사용하여 공간복잡도를 줄였다.
• 매 계산마다 1234567로 나눈 나머지를 저장하여 오버플로우를 방지했다.
• DP 문제에서도 필요한 값만 유지하면 메모리를 크게 절약할 수 있다.