[백준][python] 2193.이친수 - 동적계획법

문제

• 백준 2193.이친수 Silver III
• python
• 문제링크

2193번: 이친수

나의 코드

이 문제는 각 N의 길이 별로 생성되는 모든 이친수의 경우의 수를 직접 나열해보면 된다.

나열 결과, N = 3: 2개, N = 4: 3개, N = 5: 5개, N = 6, 8개, N = 7: 13개 .... 이렇듯 피보나치 수열이 완성된다. 단, N이 하나씩 밀려서 나타나니 N - 1에 대한 피보나치 수열을 만들어주면 된다.

N = int(input())

dp = [1, 1, 2]

N = N - 1
if N > 2:
    for i in range(3, N + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    print(dp[N])

else:
    print(dp[N])