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

문제

 

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

프로그래머스

문제풀이

 

n이 1이면 1,

n2이 2이면 1+1, 2 = 2개

n이 3이면 1+1+1, 2+1, 1+2

....

n개는 n-2의 모든 경우에서 +2를 더한 것과 같고, n-1의 모든 경우에서 +1을 더한 것과 같다.

따라서 DP[n] = DP[n-1] + DP[n-2]이다.

n이 0일 때, 1일 때는 따로 1로 값을 저장하고, 2부터는 반복문을 돌리면 된다.

나머지 연산 꼭!

 

코드

#include <string>
#include <vector>
#define DIV 1234567
using namespace std;

long long solution(int n) {
    int idx(0);
    vector<long long>DP(n + 1, 0);

    DP[0] = 1;
    DP[1] = 1;    
    for (idx = 2; idx <= n; ++idx) {
        DP[idx] = (DP[idx - 1] + DP[idx - 2]) % DIV;
    }

    return DP[n];
}