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

※ 문제

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

※ 문제 유형

다이나믹 프로그래밍 (SILVER_3)

※ 나의 풀이

• DP로 문제 해결
  • 4를 1, 2, 3으로 표현하는 방법 7가지
    • 1 + 1 + 1 + 1
    • 1 + 1 + 2
    • 1 + 2 + 1
    • 2 + 1 + 1
    • 2 + 2
    • 1 + 3
    • 3 + 1
  • 5를 1, 2, 3으로 표현하는 방법
    • 4에서 1을 더하는 방법(7가지)
    • 3에서 2를 더하는방법
    • 2에서 3을 더하는 방법
  • 6을 1, 2, 3으로 표현하는 방법
    • 5에서 1을 더하는 방법
    • 4에서 2를 더하는 방법
    • 3에서 3을 더하는 방법
• dp[N] = dp[N-1] + dp[N-2] + dp[N-3]

import sys

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

case = []
for i in range(T):
    case.append(int(sys.stdin.readline()))

# N-1 에서 1 더하기 -> N-1 을 만드는 경우의 수와 동일 == dp[N-1]
# N-2 에서 2 더하기 -> N-2 을 만드는 경우의 수와 동일 == dp[N-2]
# N-3 에서 3 더하기 -> N-3 을 만드는 경우의 수와 동일 == dp[N-3]

dp = [0] * (max(case) + 1)

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

for n in case:
    print(dp[n])