프로그래머스 (Level 2) : 멀리뛰기 / Python / dp

문제

프로그래머스

제한사항 및 입출력 예1, 2

 

1칸, 2칸을 갈 수 있을때 n칸 까지 도달하기 위한 경우의 수를 리턴하는 문제이다.

 

 n=1일때, (1칸) = return 1

n=2일때, (1칸, 1칸), (2칸) = return 2

n=3, n=4 는 그림을참고하면 된다.

 

결국 피보나치 문제였다.

 

주의할 점은 n이 1 또는 2일때 어떠한 메모리 할당도 하지 않고 바로 리턴해야 테스트1번이 통과된다.

 

 

풀이

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