[Python] 9095번 1, 2, 3 더하기

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

 

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

 

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]인 이유

→ 마지막에 더한 수가 1,2,3 중 어떤 것인지로 나눔

 

마지막에 +1를 붙였다면

→ 그 앞부분은 i-1을 만드는 방법이어야 함

→ dp[i-1]가지

 

마지막에 +2를 붙였다면

→ 그 앞부분은 i-2을 만드는 방법이어야 함

→ dp[i-2]가지

 

마지막에 +3를 붙였다면

→ 그 앞부분은 i-3을 만드는 방법이어야 함

→ dp[i-3]가지

 

따라서 dp[i]를 만들기 위해서는 dp[i-1]+dp[i-2]+dp[i-3]

 

 

 

.

.

.

어느새 백준 티어가 골드5가 되었다! 더 열심히 해야지!!