[백준/Python] 9095. 1, 2, 3 더하기 (DP)

💡 문제 요약

정수 n이 주어졌을 때,
1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.
단, 덧셈 순서가 다르면 다른 경우로 센다.

예를 들어,
4를 만드는 방법은 다음 7가지이다.

1+1+1+1  
1+1+2  
1+2+1  
2+1+1  
2+2  
1+3  
3+1

---

🧠 풀이 아이디어

이 문제는 동적 계획법(DP)으로 해결할 수 있다.
n을 만들 수 있는 경우의 수를 dp[n]이라고 하자.

마지막으로 더한 수가 1, 2, 3 중 어떤 것이냐에 따라
n을 만드는 방법은 다음 세 가지로 나뉜다.

• 마지막에 1을 더했다면 → 이전엔 n-1을 만들었을 것
• 마지막에 2를 더했다면 → 이전엔 n-2를 만들었을 것
• 마지막에 3을 더했다면 → 이전엔 n-3을 만들었을 것

즉, 점화식은 다음과 같다 👇

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

✏️ 점화식이란?

점화식은 이전 단계의 결과값으로 현재 값을 계산하는 규칙이다.
예를 들어, 피보나치 수열의 F(n)=F(n-1)+F(n-2)처럼
큰 문제를 작은 문제의 결과로 표현하는 식을 말한다.

초기값 설정

• dp[0] = 1
  → 아무 것도 더하지 않는 한 가지 경우(기준점)
• dp[1] = 1
  → (1)
• dp[2] = 2
  → (1+1), (2)

---

💻 코드

T = int(input())
MAX = 10

dp = [0] * (MAX+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2

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

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

---

🧩 코드 해설

1. dp 배열 초기화
   → 문제에서 n < 11 이므로 dp 크기를 11로 설정했다.
2. 기저값 설정
   → 0, 1, 2는 직접 계산 가능한 값으로 채운다.
3. 점화식 적용
   → 3부터는 dp[n-1] + dp[n-2] + dp[n-3]을 이용해 채운다.
4. 입력 반복
   → 테스트케이스 개수만큼 n을 입력받아 결과 출력.

⚙️ 시간 복잡도

• DP 계산: O(n)
• 각 테스트케이스 조회: O(1)

---