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

def dynamic(n):

    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    
    dp = [0]*(n+1)
    dp[1],dp[2],dp[3] = 1, 2, 4

    for i in range(4, n+1):
         dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    return dp[n]


t = int(input())

result = []

for i in range(t):
    n = int(input())
    result.append(dynamic(n))

for i in result:
    print(i)

이번 문제는 주어진 정수 N을 1, 2, 3의 합으로 만들 수 있는 경우의 수를 구하는 문제이다.

 

n=1, n=2, n=3 인 경우를 DP 테이블에 저장하고 n=4 부터는 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이라는 점화식을 도출한 뒤에 풀면 쉽게 답을 구할 수 있다 !

 

다시 한번 반성하는 것이지만 DP 알고리즘을 풀 때는 번거롭더라도 최소 n=5 까지는 경우의 수를 모두 구해보고 점화식을 도출하거나 패턴을 찾도록 하자 !