[Python] 프로그래머스 LV.03 - 멀리 뛰기

programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

[ 알고리즘 ]

DP

 

[문제 접근]

1,2만을 이용해서 n을 만드는 문제와 같다고 생각하여 바로 DP를 떠올렸다.

규칙을 찾기 위해 1~5칸 까지 종이에 그려보고, 규칙성을 찾아냈음

종이에 그려보고 바로 규칙을 찾은걸보면 DP 중엔 쉬운 문제라고 생각이 든다

 

*dp table을 [0]*(n+1) 로 하면 런타임에러가 떠서 제한 사항을 보고 [0]*(2000+1) 로 바꿔주니 해결됨

 

 

[코드]

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