[프로그래머스/python] 멀리 뛰기

[프로그래머스/python] 멀리 뛰기

멀리 뛰기

연습문제

​

문제

프로그래머스

​

풀이

다이나믹 프로그래밍 문제로서 점화식을 파악하고 진행했습니다.

1칸을 갈 경우 1가지, 2칸을 갈 경우 (1,1), (2)로 2가지 입니다.

3칸을 갈 경우 1번째 칸에서 2칸을 갈 경우와 2번째 칸에서 1칸을 갈 경우이기 때문에

이전 칸들의 경우의 수 합이 됩니다.

[ 0, 1 , 2, (1+2) ]

[ 0, 1, 2, 3, (2+3) ]

[ 0, 1, 2, 3, 5, (3+5) ]

....

풀이코드

def solution(n):
    li =[0,1,2]
    if n<3:
        return li[n]
    else:
        while(len(li)<=n):
            li.append(li[-1]+li[-2])
        return li[n]%1234567