다이나믹 프로그래밍 - 백준 9095 [Python]

Problem)

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

9095번: 1, 2, 3 더하기

 

Solution)

D[N] = D[N-1] + D[N-2] + D[N-3] 의 결과가 된다.

이때, D[0] 을 살펴봐야하는데, D[0]을 정의해야 편하게 코딩할 수 있다.

 

수를 0개 사용하는 경우는 합이 없는 경우 이므로 아무것도 사용하지 않는 경우, 1가지 이다. 따라서 D[0] = 1로 정의한다.

 

Answer)

d = [0]*11
d[0] = 1
for i in range(1, 11):
    if i-1 >= 0:
        d[i] += d[i-1]
    if i-2 >= 0:
        d[i] += d[i-2]
    if i-3 >= 0:
        d[i] += d[i-3]

t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n])