[PS] 멀리 뛰기

문제

해결

문제에 답이 나와있다. 문제를 자세히 보면 칸이 4칸일때 5가지 조합중 3가지 조합이 n이 3일때의 방법으로부터 파생된 걸 알 수 있다.

즉, 어떤 경우가 와도, i개 칸 건너기 = (1칸 & i-1칸을 뛰는 모든 경우의 수) + (2칸 & i - 2칸을 뛰는 모든 경우의 수)가 답이다.

혹시 겹치는 영역이 있나 했지만, 순서가 다르면 다른 경우이기 때문에 바로 점화식을 세울 수 있었다.

d[i] = i개의 칸을 1칸과 2칸의 조합으로 뛸 수 있는 경우의 수. 라고 한다면

d[i] = d[i-1] + d[i-2]; 이다. 다만 1234567만큼 나눠줘야한다.

소스코드

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