[백준/Python] 15989 - 1,2,3 더하기 4

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

1+1+1+1
2+1+1 (1+1+2, 1+2+1)
2+2
1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

초기 풀이
처음에는 중복 조합사용해서 문제를 풀었다
1이 n개 있는 만큼의 길이가 최대이기 때문에 itertools의 combination_with_replacement를 사용해 iterator를 [0,1,2,3]으로 두고 r을 n으로 두고 구현했었다
정답은 나오지만 combination_with_replacement의 시간복잡도가 상당히 크기 때문에 시간초과가 발생했었다
dp문제를 멀리한지가 너무 오래된 탓에 dp가 바로 떠오르지 않았고 다른 사람들의 풀이를 참고했다
초기 코드

import sys
from itertools import combinations_with_replacement

t = int(sys.stdin.readline())
iterator = [0,1,2,3]
for _ in range(t):
    n = int(sys.stdin.readline())
    cnt = 0

    for i in combinations_with_replacement(iterator, n):
        if sum(i) == n:
            cnt += 1
    print(cnt)

정답 코드

import sys

t = int(sys.stdin.readline())

dp = [1]*10001

for i in range(2,10001):
    dp[i] += dp[i-2]

for i in range(3,10001):
    dp[i] += dp[i-3]
        
for _ in range(t):
    n = int(sys.stdin.readline())
    print(dp[n])

itertools가 편하긴 하지만 코테에서 사용하기엔 너무 느려서 다른 방법을 떠올려보는 연습이 필요할듯하다