[프로그래머스/Lv. 2] 피보나치 수

🔺 문제

프로그래머스

 

🔺 코드

- 틀림

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        answer = Fibb(n) % 1234567;
        
        return answer;
    }
    
    public int Fibb(int n) {
        if(n == 0)      return 0;
        else if(n == 1) return 1;
        else            return Fibb(n - 1) + Fibb(n - 2);
    }
}

 재귀함수를 사용하려고 했는데 시간 초과가 떴다.

 

 

- 정답

import java.util.*;

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

✅ 해결 아이디어
- 동적 계획법 (Dynamic Programming) - 이미 계산한 값을 재활용함으로써, 중복 계산 피하고 계산 속도 향상
- 배열 사용.

---

🔺 다른 풀이들

프로그래머스

class Solution {
    public int solution(int n) {
        int answer = 1;
        int f1 = 0, f2 = 1;

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

        return answer;
    }
}

 

---

💬 느낀 점

이게 DP구나...!!!

아무 생각 없이 재귀 함수를 사용하면 안 되겠다.

---

(참고)

✔ 테스트 케이스 7 ~ 14 실패하는 이유

프로그래머스