[프로그래머스] 피보나치 수 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　피보나치 수를 나눈 나머지를 구하는 문제다. 일반적인 재귀 함수 방식으로 피보나치 수열을 구해서 계산하면 같은 값을 여러 번 계산하게 되기 때문에 높은 확률로 시간 초과가 걸린다. 따라서 소수를 구할 때 에라토스테네스의 체 방식으로 미리 값들을 구해놓은 것처럼, 피보나치 수도 미리 구해놓고 계산하는 다이나믹 프로그래밍 방식을 채용하면 문제를 효율적으로 해결할 수 있다.

---

풀이

#include <vector>
using namespace std;

int solution(int n)
{
    vector<int> dp(n + 1, 0);
    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];
}