[Algorithm] 프로그래머스 멀리 뛰기 | 파이썬 (DP, Dynamic Programming)

※ 멀리 뛰기

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

프로그래머스

 

문제 해결 TIP

n이 1일 때부터 생각해보자. dp[1] = 1, 2라면 1씩 2번, 2씩 1번 총 2이다. dp[3]은 (1,1,1),(2,1),(1,2) 3이다. dp[4] = 5, dp[5] = 8이므로 피보나치 수열이 떠오른다.

 

전체 코드

def solution(n):
    if n == 1: return 1
    else: 
        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 2

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

        return dp[-1]