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

9095번: 1, 2, 3 더하기

from sys import stdin
n = int(stdin.readline())
ans_list = [int(stdin.readline().strip()) for _ in range(n)]
arr = [0]*12
arr[1]=1
arr[2]=2
arr[3]=4
for i in range(4, 12) :
      arr[i] = arr[i-1]+arr[i-2]+arr[i-3]
for ans in ans_list :
      print(arr[ans])

 이번 문제도 점화식을 세우면 가볍게 해결할 수 있었다.

$$ A_n = A_{n-1} + A_{n-2} + A_{n-3} $$ 형태의 점화식을 띤다. DP 문제였고, +1, +2, +3에 따라 그 앞에 것이 무엇이든 다른 경우의 수기 때문에 저런 식을 도출할 수 있다. 고등학교 때 수열을 가장 좋아했는데, 덕분에 코딩 테스트에서도 DP가 가장 흥미로운 단원이다.