프로그래머스 - Level 2. 멀리 뛰기 / JavaScript (js)

문제설명

문제분석

이 문제는 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있습니다.

 

문제에서는 1칸 또는 2칸을 뛰어서 n칸을 뛸 수 있다고 하였으므로, n칸을 뛰기 위해서는 (n-1)칸에서 1칸을 뛰는 경우와 (n-2)칸에서 2칸을 뛰는 경우의 합과 같습니다. 이를 점화식으로 나타내면 다음과 같습니다.

 

f(n) = f(n-1) + f(n-2)

 

이해하기 쉽게 코드작성하기

function solution(n) {
  let answer = 0;
  let num1 = 1, num2 = 2;

  if (n <= 2) {
    return n;
  }

  for (let i = 3; i <= n; i++) {
    answer = (num1 + num2) % 1234567;
    num1 = num2;
    num2 = answer;
  }

  return answer;
}

이 코드를 배열을 이용해 조근 더 단순하게 나타내면 다음과 같습니다.

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