[알고리즘] 백준 9095 : 1, 2, 3 더하기 - S3

2023.05.16 풀이

import sys
input=sys.stdin.readline

t=int(input())

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

• 블로그를 참고해 풀었음

---

다른 풀이

# 원리는 같지만 짧은 풀이
dp = [0, 1, 2, 4]
for i in range(4, 11):
    dp.append(dp[-1]+dp[-2]+dp[-3])
t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n])

---

check point

• 런타임 에러 - 참고
  초깃값 잘 확인하기 !!

• DP 문제에서 점화식에 감이 잘 오지 않을 때 3개도 나열해보기. d배열의 결과값에 집중해보기.