2021.2.10 [백준] 1, 2, 3 더하기

다이나믹 프로그래밍 알고리즘

 

 

Q

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

A

 

다이나믹 프로그래밍을 이용하여 풀었으며, 점화식을 만드는데 애먹었다.

 

코드

import sys

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

array = list(int(sys.stdin.readline()) for _ in range(n))

 

d = [0] * 11 #DP 테이블 초기화
d[1] = 1
d[2] = 2
d[3] = 4

for i in range(4, 11): #범위가 중요!! n이 아니라 11까지
    d[i] = d[i-1] + d[i-2] + d[i-3] #점화식에 따른 다이나믹 프로그래밍 실행

for i in array:
    print(d[i])