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

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

코드

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

dp로 풀었다.

결국 한 지점까지 도착하는 모든 경우의 수는 한 칸전까지 도달하는 방법의 수와 두 칸 전까지 도달하는 방법의 수를 더한 것이다.

따라서 dp[i] = dp[i-1] + dp[i-2] 로 나타낼 수 있다.

dp[1]=1, dp[2]=2 라 지정해두고 그 과정을 반복하면 답을 구할 수 있다.