[Programmers] Lv2. 피보나치 수 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 전략

 

입력 데이터 범위가 최대 10만 인 걸 고려하면, 재귀로는 절대 못 구하니 DP(Dynamic Programming)으로 풀었습니다. 1234567로 나눈 나머지를 리턴하라는 걸로 보아, 오버플로우를 조심해야겠다고 생각했구요.

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;
const int DIVISION = 1234567;

int solution(int n) {
    vector<int> F(n + 1);
    F[0] = 0;
    F[1] = 1;
    
    for (int i = 2; i <= n ; i++)
        F[i] = (F[i-1] + F[i-2]) % DIVISION;
    return F[n];
}