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

문제 : www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

풀이

쉬운 문제니 보자마자 다이나믹을 떠올려야 한다.

n이라는 숫자가 있으면 n을 1, 2, 3 의 합으로 만들수 있는 경우의 수는

n-1을 1,2,3의 합으로 만드는 경우 + n-2를 1,2,3의 합으로 만드는 경우 + n-3을 1,2,3의 합으로 만드는 경우이다.

각 마이너스된 숫자에 1, 2, 3을 더하면 n이 되기 때문이다.

num에 입력을 받고 sum123에 num최대값까지 경우의 수를 입력한 다음 해당하는 부분을 출력한다.

 

n = int(input())
num = []
sum123 = []
for i in range(n):
    num.append(int(input()))

sum123=[0 for _ in range(max(num)+1)]
sum123[1] = 1
sum123[2] = 2
sum123[3] = 4

if max(num) > 4:
    for i in range(4, len(sum123)):
        sum123[i] = sum123[i-1] + sum123[i-2] + sum123[i-3]

for i in num:
    print(sum123[i])