프로그래머스 멀리 뛰기 C++

처음에는 혹시나 해서 dfs로 해봤지만 역시나 시간초과가 발생했다.

 

직접 나열해보니 규칙성을 찾을 수 있었는데

dp[ i ] = dp [ i - 1 ] + dp [ i - 2 ] 라는 점이다.

 

나중에 생각해보니 그 이유는

2칸 이전에서 뛰는 경우와 1칸 이전에서 뛰는 경우를 합치면 되기 때문이다.

#include <string>
#include <vector>

using namespace std;

int dp[2001]; // dp[i]는 i까지 가는 경우의 수


// 1 -> 1 
// 2 -> 2
// 3 -> 3
// 4 -> 5
// 5 -> 8


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