파이썬 백준 9095번: 1,2,3 더하기

문제

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

9095번: 1, 2, 3 더하기

 

 

풀이

n이 4보다 큰 경우 n을 1,2,3으로 나타내는 방법은 아래를 모두 더한 것과 같다.

1. (n-1) +1 = (n-1)을 1,2,3으로 나타내는 방법의 수

2. (n-2) +2 = (n-2)을 1,2,3으로 나타내는 방법의 수

3. (n-3)+3 = (n-3)을 1,2,3으로 나타내는 방법의 수

import sys
T=int(sys.stdin.readline())
d=[0]*12
d[1]=1
d[2]=2
d[3]=4
for _ in range(T):
    n=int(sys.stdin.readline())
    for i in range(4,n+1):
        d[i]=d[i-1]+d[i-2]+d[i-3]
    print(d[n])