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

 

 

규칙을 찾을 수 있는 dp 문제이다.

#include <string>
#include <vector>

using namespace std;

long long dp[2001];

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

/*
n = 1 -> 1
n = 2 -> 2
n = 3 -> 3
n = 4 -> 5
n = 5 -> 8

1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 1 2
2 2 1


*/