[DP] 1, 2, 3 더하기 4 - 백준

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

15989번: 1, 2, 3 더하기 4

 

동전 1과 유사한 유형으로 생각하면 된다

https://yscho.tistory.com/37

[DP] 동전 1 - 백준

 

이 두 문제는 DP의 대표적인 유형으로 N으로 표현 문제와 더불어 꼭 익혀놓자!

코드를 잘 익혀놓고

N = int(input())

num_list = [ int(input()) for _ in range(N)]
for num in num_list :
    sum_dict = {}
    for i in range(1,num+1) :
        sum_dict[i] = 1
    for j in [2,3] :
        for k in range(j, num+1) :
            if k == j :
                sum_dict[k] += 1
            else :
                sum_dict[k] += sum_dict[k-j]
    print(sum_dict[num])