[프로그래머스] 멀리 뛰기(javascript)

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

코딩테스트 연습 - 멀리 뛰기

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.

 

제한 사항

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

 

입출력 예

 

n	result
4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

풀이과정(DP)

도착지점까지 1칸 or 2칸을 점프하면서 도착한다면 결과적으로 도착지점인 N의 N - 1과 N - 2의 발판을 밟게되는 것을 이용하여 아래와 같은 식을 세웠다.

 

dp[n] = dp[n-1] + dp[n-2] 

 

 

소스코드

function solution(n) {
    var dp = new Array(n + 1);
    dp.fill(-1);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    function solve(cur) {
      if (dp[cur] != -1) return dp[cur];
      dp[cur] = 0;
      if (cur - 1 > 0) dp[cur] += (solve(cur - 1)%1234567);
      if (cur - 2 > 0) dp[cur] = (dp[cur] + solve(cur - 2)%1234567);
      return dp[cur]%1234567;
    }
    return solve(n);
}