프로그래머스 lv2 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=cpp 

프로그래머스

이 문제의 경우 백준의 dp문제에 항상 시달리던내가 풀기에도 쉬운 문제였다 처음 이문제를 풀때는 dfs로 접근해볼까라는 생각을 하고 풀어보았다 하지만 dfs의 특징상 하나한 다해보기때문에 경우의 수가 기하급수적으로 늘어나 시간복잡도가 무지막지하게 늘어나는 현상을 보여주었기 떄문에 결국에 이전값을 사용하는 dp로 이문제를 풀었다 이문제의 경우 어떠한 발판에 도착하는  경우의 수는 총 2가지이다 내 2번째  전 발판에서 오거나 내 저에 발판에서 오거나 이다. 2번째 발판 전도 마찬가지고 전 발판들도 똑같다 즉 나까지 도착하는 경우의수는 내 2번째전 발판까지 오는 경우의수와 나의 전 발판 까지 오는 경우의 수의 합이다. 이에 점화식은 

 dp[i] = (dp[i - 1] + dp[i - 2]) 이것이다

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