[백준] 9095번: 1, 2, 3 더하기 문제 풀이 파이썬

문제 링크

https://www.acmicpc.net/problem/9095

풀이 방식

1. 정수 4의 경우의 수는 7(1+2+4)이고, 5의 경우의 수는 13(2+4+7)인걸 확인 가능하다.
2. 따라서 정수 N의 경우의 수는 (N-3) + (N-2) + (N-1)의 합으로, 다음과 같은 점화식을 세울 수 있다.

   점화식
   dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
   or
   dp[n] = sum(dp[i-3:i])

전체 코드

T = int(input())
for _ in range(T):
    N = int(input())
    dp = [1, 2, 4]
    for i in range(3, N):
        dp.append(sum(dp[i-3:i]))
    print(dp[N-1])