[프로그래머스 | 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하면 됩니다.

💯성공한 풀이💯

const solution = (n) => {
    return fibonacci(n);
}

const fibonacci = (n) => {
    const dp = new Array(n+1).fill(0);
    dp[0] = 1; dp[1] = 1;
    
    for(let i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
    }
    
    return dp[n];
}

처음 문제를 보았을때 dfs 문제인가? 라고 생각했었다.
접근 방식이 잘못되었다는 것을 깨달았고, dp 문제라는것을 알았다.
보통 1234567로 나눈 나머지를 구하라고 하면 dp 문제이다.

문제를 살펴보자
뛸 수 있는 칸이 1칸 또는 2칸이다.

1칸을 뛰어야 할 때

• 1칸을 뛴다.
  => 1가지 방법

2칸을 뛰어야 할 때

• 1칸, 1칸을 뛴다.
• 2칸을 뛴다.
  => 2가지 방법

3칸을 뛰어야 할때

• 1칸, 1칸, 1칸을 뛴다.
• 1칸, 2칸을 뛴다.
• 2칸, 1칸을 뛴다.
  => 3가지 방법

4칸을 뛰어야 할 때

• 1칸, 1칸, 1칸, 1칸
• 1칸, 2칸, 1칸
• 1칸, 1칸, 2칸
• 2칸, 1칸, 1칸
• 2칸, 2칸
  => 5가지 방법

칸 별로 뛰어야 하는 방식을 나열해보면 1, 2, 3, 5 피보나치 수열이다.
피보나치 수열의 점화식은 dp[i] = dp[i - 2] + dp[i - 1] 이다.