[백준][DP] 9095. 1,2,3 더하기

9095. 1,2,3 더하기

9095번: 1, 2, 3 더하기

 

• 풀이

직접 계산한 결과
dp[1]=1
dp[2]=2
dp[3]=4 : [1+1+1+1] / [2+1] *3
dp[4]=7 : [1+1+1+1+1] / [2+1+1] *3 / 2+2 / [3+1] *2
dp[5]= 13 : [1+1+1+1+1] / [2+1+1+1] *4 / [2+2+1] *3 / [3+1+1] *3 / [2+3] *2
dp[6]= 24

 

→ i>=4 일때, dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

1,2,3으로 N을 만드는 논리적 풀이는 
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
(1) [N-1] + 1 을 하는 것 : dp[i-1] 수와 동일
(2) [N-2]+2 을 하는 것 :  dp[i-2] 수와 동일
(3) [N-3] +3 을 하는 것 :  dp[i-3] 수와 동일

 

 

T = int(input())
for _ in range(T):
    n = int(input())
    dp = [0 for _ in range(12)]
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for i in range(4, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

    print(dp[n])