[DP] 백준 #9095 1, 2, 3 더하기 - Python

🗂️ 문제

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

9095번: 1, 2, 3 더하기

 

💡 접근법

1을 만드는 방법은 1가지이고,

2를 만드는 방법은 (1+1), (2)로 2가지이고,

3을 만드는 방법은 (1+1+1), (2+1)*2, (3)으로 4가지이고,

4를 만드는 방법은 (1+1+1+1), (1+1+2)*3, (1+3)*2, (2+2)로 7가지이고,

5를 만드는 방법은 (1+1+1+1+1), (1+1+1+2)*4, (1+2+2)*3, (3+1+1)*3, (3+2)*2로 13가지이다.

이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] (N>3)이다.

 

😎 내 코드

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    dp = [0] * (N+1)

    for i in range(1, N+1):
        if i == 1:
            dp[1] = 1
        elif i == 2:
            dp[2] = 2
        elif i == 3:
            dp[3] = 4
        else:
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[N])

 

✅ 정답 확인