EDOC 2024-1 5회차 정모 (동적 계획법 알아보기 2)

A. 1, 2, 3 더하기 (백준 9095번)

 

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

 

#python

import sys
input = sys.stdin.readline

t = int(input())
dp = [0] * 12

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

for _ in range(t):
    n = int(input())
    print(dp[n])

n을 1, 2, 3의 합으로 나타내려면 다음과 같은 경우의 수가 있다. (여기서 주의할 점은 1+2와 2+1가 다른 경우라는 것이다.)

1) (n-1)까지 만들고 1을 더하기

2) (n-2)까지 만들고 2를 더하기

3) (n-3)까지 만들고 3을 더하기

점화식 : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

(정답)