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

주어진 n칸에 딱 도착할 수 있는 경우의 수를 계산해서 조건에 맞게 리턴해주면 되는 문제이다. 문제의 흐름을 따라가다보면 i번째에 도달하는 경우는 i-1 에서 한칸이동 + i-2 에서 두칸이동 한 결과라는 것을 알 수 있다.

#include <string>
#include <vector>

using namespace std;

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