[ 프로그래머스 ] 멀리 뛰기

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12914

풀이

---

피보나치 수열 형태의 문제로, 이전 값들의 합으로 현재 값을 구할 수 있다. 다만 재귀로 풀면 시간 초과가 날 가능성이 높으므로, DP(동적계획법)을 사용해 풀었다.

#include <string>
#include <vector>

using namespace std;

long long solution(int n) 
{
    long long answer = 0;

    int dp[2001];
    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i <= n; i++)
    {
        dp[i] =( dp[i - 1] + dp[i - 2] ) % 1234567;
    }
    answer = dp[n - 1];

    return answer;
}