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

백준9095번 바로가기

정말 dp스럽게 접근해야 하는 문제, 점화식을 잘 세우는게 문제의 전부다.
이전의 값을 어떻게 활용할 것인지 고민하며 문제를 풀었다.

1,2,3을 더해 i값을 표현하는 경우의 합을 구하려면

(1,2,3을 더해 i-1값을 표현하는 경우의 합)
+(1,2,3을 더해 i-2값을 표현하는 경우의 합)
+(1,2,3을 더해 i-3값을 표현하는 경우의 합)
을 하면 자연스럽게 1,2,3을 더해 i값을 표현하는 경우의 합이 구해지면서 연속적으로 문제가 해결된다.

따라서 a(i)=a(i-1)+a(i-2)+a(i-3) 이라는 점화식이 도출되었다.

a(3)까지는 위 점화식을 따르지 않으므로 값을 직접 고정시키고 4번째 값부터 반복문을 통해 구한다.

import sys

input=sys.stdin.readline

t=int(input())
for _ in range(t):
  n=int(input())
  def dp(n):
    d=[0]*12
    d[0]=0
    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]
    return d[n]

  print(dp(n))