백준 9095번 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

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

n=1부터 차근차근 경우를 구해보면 점화식을 얻을 수 있다.

 

n=1 : 1 -> 1가지

n=2 : 1+1 /  2 -> 2가지

n=3 : 1+1+1 / 1+2 / 2+1 / 3 -> 4가지

n=4 : 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1 -> 7가지

n=5 : 1+1+1+1+1 / 1+1+1+2 / 1+1+2+1 / 1+2+1+1 / 2+1+1+1 / 1+2+2 / 2+1+2 / 2+2+1 / 1+1+3 / 1+3+1 / 3+1+1 / 2+3 / 3+2 -> 13가지

...

우리가 사용할 수 있는 조합은 1,2,3의 경우로

n=4부터 DP[N] = DP[N-1] + DP[N-2] + DP[N-3]으로 이루어지는것을 볼 수 있다.

 

검산을 위해 n=7, 10을 구해보면 값이 일치하는것을 알 수 있다.

 

이를 파이썬 코드로 나타내면 다음과 같다. (테스트 케이스 수를 먼저 입력받고, index일치를 위해 맨 처음 0을 넣어줌에 유의한다)

T = int(input())
for i in range(T):
    n = int(input())
 
    #dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
    dp = [0,1,2,4]
 
    for j in range(4,n+1):
        dp.append(dp[j-1] + dp[j-2] + dp[j-3])
 
    print(dp[n])