[ Programmers ] lv2_멀리 뛰기(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 이하인 정수입니다.

 

풀이

도달할 수 있는 방법의 수를 저장할 배열생성 -> dp
n+1개의 요소를 가진 배열 dp를 생성하고, 모든 요소를 0으로 초기화해준다.
dp[1] = 1;, dp[2] = 2;: 한 칸일 때와 두 칸일 때의 방법의 수를 각각 1과 2로 초기화합니다.
포문을 이용하여 1과 2의 초기값이 설정되어있기 때문에 i를  3부터 n까지의 범위에서 반복문을 실행
(i는 현재 위치를 의미)
현재 위치인 i 칸까지 도달할 수 있는 방법의 수를 구한다. -> i -1 + i -2 를 현재 i칸에 저장하면서  % 1234567를 해줌
 % 1234567은 결과값을 작은 수로 제한하기 위해 사용되는 나머지 연산이다.
최종적으로 n 칸까지 도달할 수 있는 방법의 수인 dp[n]을 반환한다.

 

코드

// 한번에 1칸, 또는 2칸밖에 이동 가능
// dp로 구현 / 피보나치 수와 비슷한 형식
function solution(n) {
  // DP 배열 초기화 
  const dp = Array(n+1).fill(0);
  // 한칸일때, 두칸일때 방법의 수 설정
  dp[1] = 1; 
  dp[2] = 2; 
  // DP 배열을 이용하여 나머지 칸에 대한 방법의 수 구하기
  // 1,2는 이미 설정되어있기 때문에 i = 3부터 시작
  for (let i = 3; i <= n; i++) {
    // i-1 칸과 i-2 칸의 방법의 수를 더하여 저장
    // % 1234567 하는 이유 : 결과값을 작은 수로 제한하기 위함 (시간복잡도 등)
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
  }
  // 최종적으로 마지막에 저장된 방법의 수를 리턴
  return dp[n];
}