[CodeKata] 프로그래머스(Lv3) : 멀리 뛰기

🥋 Oooth More!! (Level 3) 

 

 

🧮 풀이

정답의 규칙성을 확인해보니 DP(Dynamic Programming) 으로 풀 수 있는 문제였다.

효진이는 1칸 혹은 2칸만 뛸 수 있다. 4칸을 뛴다고 가정하면, (2칸을 뛰는 모든 경우 + 2칸 뛰기), (3칸을 뛰는 모든 경우 + 1칸 뛰기) 둘의 합으로 결과를 산출할 수 있기 때문이다.

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

• dp는 동적 계산법 결과들을 누적하는 배열이다. index번째 값이, index 칸만큼 뛰는 모든 경우의 수가 된다.
• 0번째는 고려하지 않아 0으로 넣었고, 1번째는 1가지(1칸), 2번째는 2가지(1칸+1칸, 2칸) 으로 초기화하였다.
• 3번째부터 n번째까지, dp[i]를 dp[i-1] + dp[i-2] 의 합으로 누적한다. 이 때, Int 오버플로우가 발생하므로 1234567로 나눈 나머지로 누적한다.
• dp[n]이 n칸까지 가는 모든 방법의 수이다.(1234567로 나눈 나머지) 이를 반환한다.

 

🖇 리뷰

1~2주 전에 풀었던 문제들이 DP 고난이도 문제들인데 반해, 이번 문제는 완전 기본적인 DP여서 구현하는데 어려움이 없었다.

 

동적 프로그래밍의 원리 자체는 어렵지 않다. 전과 전전의 연산값을 참고해, 현재의 연산값을 누적해나가는 방법이다. (ex) 피보나치 수열)

* DP(Dynamic Programming) 참고링크 : https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP