[프로그래머스] 멀리 뛰기 (파이썬)

문제

풀이 

위 문제는 현재 위치에서 한 칸 가거나 두 칸 가서 끝까지 가려면 얼마나 가야하는지 구하는 문제다.

처음에는 재귀와 DP를 섞어서 문제를 풀었으나 재귀를 너무 깊게 호출해서 런타임 에러가 발생했다.

그렇기에 다른 사람들의 코드를 참고하였다.

아래 풀이는 피보나치 수열처럼 접근한 문제이다. 생각해보면 어차피 앞으로 두칸 혹은 한칸만 이동할수 있기에 현재 위치 까지 오기까지 나의 위치 - 2 까지 올수있는 방법 + 나의 위치 - 1 까지 올수있는 방법을 더한것과 동일하다.

 

코드

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