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

 이 문제는 다이나믹 프로그래밍을 이용한 문제이다. 입력이 최대 2000인 자연수이므로 배열로 선언하기 좋은 크기이고, 경우의 수가 매우 많아 완전 탐색으로는 중복된 경우가 많이 생기기 때문에 다이나믹 프로그래밍을 사용하면 좋다.

 

 이 문제의 경우 점화식은

dp[1] = 1
dp[2] = 2
dp[k] = (dp[k - 1] + dp[k - 2]) % 1234567 (k >= 3)

이 된다. 

 

 헷갈렸던 점은 1칸 전까지 오면 1가지의 경우의 수 밖에 없지만, 2칸 전까지 오면 1 1 로 오는 것과 2 한번에 오는 두가지 경우가 있지 않나하는 것이었다. 그러나 이는 중복 경우를 셀 수 밖에 없는데, 전부 한칸씩 오는 경우가 dp[k - 1]과 dp[k - 2]에 모두 해당되어 있기 때문에 dp[k - 2] 에서는 2칸을 한번에 오는 경우만 세어야 중복이 없다.

 

 

#include <string>
#include <vector>

using namespace std;

#define MOD 1234567

long long dp[2001];

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]) % MOD;  
    }
    
    answer = dp[n];
    
    return answer;
}