프로그래머스[Level 2] 멀리 뛰기 (dp)

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

n은 1 이상, 2000 이하인 정수입니다.

입출력 예

풀이

function solution(n) {
    const dp = [0, 1, 2, 3];
    for(let i=4;i<=n;i++){
        dp[i] = (dp[i-1] + dp[i -2]) % 1234567;
    }
    return dp[n] % 1234567;
}

1 또는 2만 사용할 수 있는 걸 보고, 계단 오르기 문제를 떠올려서 dp로 풀었다.

dp문제는 거꾸로 생각하는 것이 도움이 된다.

1번 칸에서 뒤를 돌아보자, 시작점으로 되돌아갈 방법은 1개 뿐이다.

2번 칸에서 뒤를 돌아보자, 시작점으로 되돌아갈 방법은 한번에 돌아가거나 1번칸에 갔다가 가는 방법 2개뿐이다.

3번 칸에서 뒤를 돌아보자, 2번칸으로 가거나 1번칸으로 가는 방법이 있다. 2번으로가면 2가지의 방법이 있을 것이고, 1번으로 가면 1가지 방법이 있을 것이다.
즉, 2번 칸에서 돌아가는 방법의 수 + 1번 칸에서 돌아가는 방법의 수가 3번 칸에서 돌아가는 방법의 수가 된다.