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

문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/12914

사고 과정

• 칸이 한 칸만 있을 때: (1칸) (방법 1가지)
• 칸이 두 칸 있을 때: (1칸, 1칸), (2칸) (방법 2가지)
• 칸이 세 칸 있을 때: (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸)(방법 3가지)
• 칸이 네 칸 있을 때 : (1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸) (방법 5가지)
• 이런 식으로 두 번째 전의 방법 수와 바로 전의 방법 수를 더하면 답이 나오는 DP 문제다.

나의 풀이

def solution(n):
    a = [0 for _ in range(n+2)]
    a[1] = 1
    a[2] = 2
    for i in range(3, n+1):
        a[i] = (a[i-2]+a[i-1])%1234567
    return a[n]