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

[문제 링크]

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

프로그래머스

[문제 고민]

• 우선 1칸씩 가는 것은 무족건 포함되어야 하므로 경우의 수는 1부터 시작이라고 생각
• 몫과 나머지로 풀어보려고 했음.. (삽질인건 안비밀..) 대충 아래와 같은 논리인데 2개의 테스트 케이스는 맞췄으나.. 나머지 다 틀린걸 보면 뭔가 논리에 허점이 있었다 ㅠ
• (ex) 3의 경우 - 1칸씩 가는 1 1 1 [1개] + (3//2= 1) + (3 - (2 ** (3//2) = 1) [2개]  = 총 3개의 경우의 수

[핵심 개념]

• DP (Dynamic Programming) → '점화식' 활용 (ex) 피보나치 수 f(n) = f(n-1) + f(n-2)

[추가 끄적]

• 피보나치 수라는 것을 생각 못해낸게 babogata...

[작성 코드]

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