[문제 풀이] 멀리 뛰기 LV 2. - DP

요구사항

문제 풀이

def solution(n):
    if n <= 2:
        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

• n이 1일경우 [1] - 1가지
• n이 2일경우 [1,1], [2] - 2가지
• n이 3일경우 [1,1,1], [2,1], [1,2] - 3가지
• n이 4일경우 [1,1,1,1], [2,1,1], [1,2,1], [1,1,2], [2,2] - 5가지
• n이 5일경우 [1,1,1,1,1], [2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2], [2,2,1], [2,1,2], [1,2,2] - 8가지

F(n) = F(n−1) + F(n−2) 피보나치 수열과 같다는것을 파악해서 F(1) = 1, F(2) = 2 이후 부터 n번째 인덱스 값을 찾아서 return해 주면 된다.