백준 9095번 - 1, 2, 3 더하기 파이썬

📌 백준 9095번 - 1, 2, 3 더하기 (DP)

✨ 문제 요약

정수 n이 주어졌을 때, 정수 1, 2, 3을 사용해서 합이 n이 되는 경우의 수를 구하는 문제입니다.
순서를 고려한다는 것이 핵심입니다.

🧠 문제 해석

이 문제는 순서를 고려한 경우의 수 DP 문제입니다. 각 숫자는 다음의 경우들로 쌓일 수 있습니다:

• 마지막에 +1 을 붙이면 → dp[i-1]
• 마지막에 +2 을 붙이면 → dp[i-2]
• 마지막에 +3 을 붙이면 → dp[i-3]

🔧 점화식

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

🧱 DP 테이블 예시

i	dp[i]	의미
1	1	1 → 1가지
2	2	1+1, 2 → 2가지
3	4	1+1+1, 1+2, 2+1, 3
4	7	총 7가지

✅ 코드

t = int(input())
for _ in range(t):
    n = int(input())
    dp = [0] * (n + 1)
    if n >= 1: dp[1] = 1
    if n >= 2: dp[2] = 2
    if n >= 3: dp[3] = 4
    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    print(dp[n])

🧩 배운 점

• DP 테이블은 의미 정의가 중요하다.
• 이 문제는 조합이 아니라 순서 있는 경우의 수 문제다.
• 초기값 설정(dp[1] ~ dp[3])이 핵심!

🎓 정리

항목	내용
문제 유형	DP (경우의 수)
점화식	dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
초기값	dp[1] = 1, dp[2] = 2, dp[3] = 4
주의점	순서를 고려한다는 점

🏷 해시태그

#DP #동적계획법 #백준9095 #1_2_3더하기 #경우의수 #점화식 #파이썬DP #백준Python #알고리즘공부