Algorithm/Baekjoon
[DP] 백준 #9095 1, 2, 3 더하기 - Python
jyjyjy25
2024. 4. 9. 00:17
🗂️ 문제
링크: https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
💡 접근법
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])