[프로그래머스] LV.3 멀리 뛰기 (JS)

문제

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

입출력 예시

n	result
4	5
3	3

풀이

해당 문제를 보고 어디선가 비슷한 문제를 보거나 풀어본 것 같다고 느낀다면 이전 포스트를 참고하자. 이 문제를 미리 풀어보았다면 해당 문제가 위 포스트의 문제와 동일하다는 것을 알 수 있을 것이다.

그러나 이 문제를 처음 접한 사람들을 위해 처음부터 설명해보자. 효진이는 멀리 뛰기를 1칸 또는 2칸 밖에 할 수가 없다. 우리는 이 점에 집중을 해야한다. 문제의 예시는 4칸이 주어졌을때 효진이가 뛸 수 있는 방법이 총 5가지로 제시되어 있다. 그러나 우리는 1칸부터 4칸까지 효진이가 뛸 수 있는 방식을 모두 찬찬히 살펴보자.

1. 1칸을 뛰어야 할 때 : 1가지

   • 이 경우 효진이는 1칸을 뛸 수 밖에 없다.

2. 2칸을 뛰어야 할 때 : 2가지

   • 1칸씩 두 번 뛸 수 있다.
   • 2칸을 한 번에 뛸 수 있다.

3. 3칸을 뛰어야 할 때 : 3가지

   • 1칸씩 세 번 뛸 수 있다.
   • 1칸을 한 번 뛰고 두 칸을 한 번 뛸 수 있다.
   • 1칸을 두 번 뛰고 두 칸을 한 번 뛸 수 있다.

4. 4칸을 뛰어야 할 때 : 5가지

   • 위 문제 설명에 제시된 바와 같다.

눈썰미가 좋은 사람은 칸이 한 칸씩 늘어날 때 마다 반환되는 수열이 피보나치 수열이라는 점을 눈치챘을 수도 있다. 따라서 해당 문제는 피보나치 수열을 구하면 된다. 그런데 이때 1234567을 나눈 나머지를 리턴하도록 제한하고 있다. 이 같은 경우는 대부분 DP를 이용하라는 팁 아닌 팁과도 같다. 보통 피보나치를 재귀함수로 구하는 법을 입문으로 접하게 되는데 이 경우 불필요한 연산이 중복되어 시간복잡도와 함수 호출 스택에 무리가 많이간다. 관련 설명은 위에 링크를 건 포스티 또는 구글에 검색하면 자료가 많이 있다. 따라서 문제의 풀이는 피보나치를 DP를 이용하여 구하기가 된다.

근데 왜 위의 과정이 결국 피보나치 수열로 이어지는지 궁금할 수 있다. 해당 설명 역시 이전 포스트에 좀 더 자세히 설명되어 있다. 때문에 여기선 간단히만 설명하자면 다음과 같다.

1. 1칸을 뛰어야 할 때 => 1가지 경우가 고정

2. 2칸을 뛰어야 할 때 => 2가지 경우가 고정

3. 3칸을 뛰어야 할 때 => DP[3] = DP[2] + DP[1]

   • 1칸을 뛸 수 있음 : 이 경우 2칸이 남음

     • 2칸을 뛰어야 하는 경우를 이미 이전에 계산함
     • 새로 계산없이 이전 결과를 그대로 활용 가능

   • 2칸을 뛸 수 있음 : 이 경우 1칸이 남음

     • 1칸을 뛰어야 하는 경우를 이미 이전에 계산함
     • 새로 계산없이 이전 결과를 그대로 활용 가능

4. 4칸을 뛰어야 할 때 => DP[4] = DP[3] + DP[2]

즉 다음과 같은 점화식을 도출 할 수 있다.

• DP[i] = DP[i-2] + DP[i-1]

그리고 위 점화식은 피보나치 수열을 구할 때 사용하는 점화식이기도 하다. 1234567을 나눈 나머지를 저장해야 한다는 것에 주의하며 구현하면 된다. 관련 코드는 이미 이전 포스트에 구현한 바 있으므로 바로 전체코드를 보도록 하자.

코드

function 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];
}

출처

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