[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬

[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬

[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬

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

9095번: 1, 2, 3 더하기

 

풀이

주어진 숫자를 1, 2, 3 으로 표현하는 경우의 수는 점화식으로 표현 가능하다.

 

dp(1) = 1

dp(2) = 2

dp(3) = 4

dp(4) = dp(1) + dp(2) + dp(3)

dp(N) = dp(N-3) + dp(N-2) + dp(N-1)

 

N = int(input())

nums = [0, 1, 2, 4]

for _ in range(4, 12):
    nums.append(sum(nums[-3:]))

for _ in range(N):
    print(nums[int(input())])