백준 15989번(G5): 1, 2, 3 더하기 4

문제

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

 

풀이

먼저 합을 이루는 수의 순서만 다른 것은 같은것으로 치므로, 합을 이루는 가장 큰 수를 이용해 분류할 수 있다.
따라서 DP[i][j] 를 $i$를 합으로 나타낼 때 가장 큰 수는 $j$인 경우의 수 라고 정의하자.

그러면 정의에 따라 $i-j$가 되는 수를 $j$ 이하인 수의 합으로 나타내는 경우의 수와 같으므로 다음이 성립한다.

$$DP[i][j] = \sum_{k=0}^{j} DP[i-j][k]$$

이제 그러면 $DP[n][1] + DP[n][2] + DP[n][3]$ 가 원하는 답이 된다.

여담

해당 알고리즘은 $O(n)$ 로 실행되고, $n$은 $10000$ 이하이기 때문에, 각 입력마다 위 알고리즘을 실행하는 대신 한번에 $10000$ 까지 계산한 후 입력에 대해 DP 배열의 값을 불러오도록 하는 편이 좋다.

제출 코드

import sys

def input(): return sys.stdin.readline().strip()
def print(com, end="\n") : return sys.stdout.write(str(com) + end)
def INT(n=0) : return int(input())+n
def ARRAY( n,m , ini = 0) : return [[ini]*m for _ in range(n)]

T = INT()

def solve(n):
    dp = ARRAY(n+2 , 4)
    
    dp[1][1] = 1
    dp[2][1] = 1
    dp[2][2] = 1
    dp[3][1] = 1
    dp[3][2] = 1
    dp[3][3] = 1
    
    
    for i in range(4, n+2):
        for k in [1,2,3]:
            dp[i][k] = sum([dp[i-k][j]  for j in range(1,k+1)])
    return dp
ANS = solve(10000)

for _ in range(T):
    n=  INT()
    print( ANS[n][1]+ANS[n][2]+ANS[n][3] )