[Python 3] BOJ 15989 1,2,3 더하기 4

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

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

 

전형적인 다이내믹 프로그래밍 문제이다.

 

 

t=int(input())
for _ in range(t):
    n=int(input())
    dp=[[1e10,0,0,0] for _ in range(10001)]
    dp[1][1]=1
    dp[2][1]=1
    dp[2][2]=1
    dp[3][1]=2
    dp[3][3]=1
    if n<=3:
        print(sum(dp[n][1:]))
        continue
    for i in range(4,n+1):
        for j in range(1,4):
            if j==1:
                dp[i][1]=dp[i-1][1]+dp[i-1][2]+dp[i-1][3]
            elif j==2:
                dp[i][2]=dp[i-2][3]+dp[i-2][2]
            else:
                dp[i][3]=dp[i-3][3]
    print(sum(dp[n][1:]))

 

dp의 정의를 dp[ 만드는 목표 숫자 ] [ 사용한 숫자 중 제일 작은 숫자 ] 로 정의하였다.

예를 들어서, dp [9][3] 은 3+3+3, 즉 한 개를 의미하고, dp[9][2]는 3+2+2+2와 같이, 사용한 제일 작은 숫자가 2인 경우, 즉 한 가지를 의미한다. dp[9][1]은 3+3+2+1 부터 1을 9개 더한 것 까지 포함하는 모든 경우를 포함한다.

즉, 9일 때의 정답은 dp[9][3]+dp[9][2]+dp[9][1]이다.