[BOJ] 9095. 1, 2, 3 더하기

📌 문제 제목

문제 링크: BOJ 9095

---

🗒️ 문제 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하여라.

e.g. 4를 1, 2, 3으로 나타내는 방법은 총 7가지 이다.

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

시간 제한: 1초

메모리 제한: 512MB

1 <= N < 11

---

💡 문제 해결 아이디어

• 테이블 정의
  • d[i]는 i를 1, 2, 3으로 만들 수 있는 방법의 수
• 점화식 찾기
  • d[4]
    • 1+1+1+1, 1+2+1, 2+1+1, 3+1 -> d[3]을 만드는 방법 + 1
    • 1+1+2, 2+2 -> d[2]를 만드는 방법 + 2
    • 1+3 -> d[1]을 만드는 방법 + 3
    • ※ d[4] = d[1] + d[2] + d[3]
• 초기값 정하기
  • d[1] = 1
  • d[2] = 2
  • d[3] = 4

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

t = int(input().strip())

dp = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0]

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

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