멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

효진이가 멀리 뛰기를 할 때,
주어진 칸 수 ( n )에 도달하는 방법의 수를 계산하는 문제

효진이는 한 번에 1칸 또는 2칸을 뛸 수 있으므로,
이 문제는 동적 프로그래밍(Dynamic Programming)으로 해결 가능

def solution(n):
    MOD = 1234567
    if n == 1:
        return 1
    elif n == 2:
        return 2
    
    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]) % MOD
    
    return dp[n]

dp[i-1]은 마지막 칸에서 1칸 뛴 경우
dp[i-2]는 마지막 칸에서 2칸 뛴 경우