[Javascript][Python] 프로그래머스 LV2 멀리 뛰기

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

프로그래머스

 

- 문제 파악

1. 한 번에 1칸 또는 2칸 이동 가능하다.
2. n칸까지 이동할 수 있는 방법의 개수를 return

 

- 문제 해결 흐름

1. 전형적인 dynamic programming의 bottom-up 방식 유형의 풀이로 해결가능한 문제다.

 

문제에서 제시한 조건 중 1칸과 2칸 이동으로 제한이 되어 있기 때문에

4번 째 칸까지 이동하기 위해서 올 수 있는 방법은 

- 3번째 칸에서 한 칸 이동하여 4번 째 칸에 도착

- 2번째 칸에서 두 칸 이동하여 4번 째 칸에 도착

즉,

2번 째 칸까지 이동하는 방법의 개수(2) + 3번 째 칸까지 이동하는 방법의 개수(3)이다.

dp 유형은 점화식을 구하는 것이 문제 해결의 핵심인데 

f(n) = f(n-2) + f(n-1) // (단, n > 1) 

피보나치 수의 점화식과 동일하다.

Python

def solution(n):
    dp_array = [0 for _ in range(n+1)]
    dp_array[1] = 1
    if(n == 1):
        return 1
    dp_array[2] = 2

    for i in range(3, n+1):
        dp_array[i] = dp_array[i-1] + dp_array[i-2]

    return dp_array[n] % 1234567

 

Javascript

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

 

비슷한 유형의 문제

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기