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

멀리 뛰기

문제 설명

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

사고과정

1. 처음 이 문제를 접근했을때에는 2의 개수와 2의 배수인지에 따라 계산을 하는 공식을 작성하다가 실패했습니다.
2. 문제를 다시 살펴본 결과, 특정 경우의 수를 누적하면서 최종적인 경우의 수를 계산하는 방법임을 알았습니다.
3. 3일때의 경우의 수, 4일때의 경우의 수 등 7일때까지 값을 구해봤을 때 피보나치의 형태를 띈다는 것을 알고, dp에 적용하여 dp[n] = dp[n - 1] + dp[n - 2]의 점화식으로 작성하여 문제를 해결했습니다.

코드

function solution(n) {
    var answer = 1;
    
    let dp = Array.from(Array(n + 1), () => 0);
    dp[1] = 1;
    dp[2] = 2;
    
    for(let i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
    
    return dp[n];
}

점화식 해석

점화식을 도출하고 나서, 다시 생각해보니 피보나치로 경우의 수가 늘어나는 이유를 모르겠어서 다른 분들의 코드와 해석을 보고 다시 정리해보았습니다.

1. n = 1일 때, 그 칸에 도달할 수 있는 경우의 수 => [1], 1개
2. n = 2일 때, 그 칸에 도달할 수 있는 경우의 수 => [11, 2], 2개
3. n = 3일 때는 두 가지 경우로 접근할 수 있습니다.
   • 1칸을 뛰어서 오는 경우
   • 2칸을 뛰어서 오는 경우
4. 1칸을 뛰어서 오는 경우는 n - 1의 경우의 수를 의미합니다.
   마찬가지로, 2칸을 뛰어서 오는 경우는 n - 2의 경우의 수를 의미합니다.
5. 따라서, n = 3일 때의 경우의 수는 1 + 2 = 3개 입니다.
6. 이를 점화식으로 풀이하면 dp[n] = dp[n - 1] + dp[n - 2]입니다.

풀이 후기

오랜만에 정통 dp 문제를 풀이한 거 같습니다.
원래도 dp 점화식을 만드는게 어려웠지만, 이번에는 점화식 도출까지는 크게 어렵지 않았으나 도대체 어떤 근거로 이런 결과가 만들어지는지 명확히 해석되지 못했습니다.

이미 문제를 풀이하셨던 많은 분들의 코드와 설명으로 문제의 정답을 확실히 이해할 수 있었던 좋은 시간이였습니다.