[프로그래머스] Level2 : 멀리 뛰기[Python]

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

프로그래머스

풀이 :

1. 어떻게 풀어야 할지 곰곰히 생각해보다가 그래프 x , 그리디 x , DP 인가?? 라고 생각해서 점화식을 구해봄

2. n이 1부터 6까지 일때 각 방법의 개수를 구해보니 i > 2일때, dp[n] = dp[n-2] + dp[n-1]이라는 점화식을 구할 수 있었음

 

코드 :

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