[백준] 9095. 1, 2, 3 더하기 - 파이썬

문제

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

9095번: 1, 2, 3 더하기

설계

- DP

- 주어진 수의 3가지 경우의 수를 묶어 더하면 해당 수의 경우의 수를 나타낸다.

# 1 2 3 4 5... (number)
# 1 2 4 7 13... (total)

# 1 + 2 + 4 = 7
# 2 + 4 + 7 = 13

N = int(input())
arr = [int(input()) for _ in range(N)]

for i in range(N):
    number = [1, 2, 4]

    if arr[i] <= 3:
        print(number[arr[i] - 1])
    else:
        for j in range(arr[i] - 3):
            number.append(sum(number[0 + j:3 + j]))
        print(number[-1])