프로그래머스 Lv2 멀리 뛰기 (python)

멀리 뛰기

풀이

처음엔 재귀로 했으나, 이번에도 maximum에 걸렸다.

dp를 이용했다.
현재 칸의 경우의 수는 1칸 전과 2칸 전의 경우의 수를 합친 것과 같다는 것에 기인했다.
그러니 아래처럼 코드가 나왔따.

def solution(n):
    # n번 칸에 도착할 수 있는 경우의 수는 1칸 전에서의 경우의 수와 2칸 전의 경우의 수를 더한 것.
    dp = [0,1,2] + [0] * 1998
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n] % 1234567

다른 사람 풀이

다들 비슷비슷하게 풀었다.

def solution(n):
    dp = [0]*2002
    dp[1], dp[2] = 1, 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2])%1234567
    return dp[n]