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

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

9095번: 1, 2, 3 더하기

간단한 DP 문제다.

1,2,3 더하기 시리즈 문제를 보면, 여러 제약조건이 생기면서 (같은 번호 2개이상 붙이면 안된다 같은 조건) 힘들어지는데 그런 조건이 없다.

이런 조건이 없는 경우, 다음 점화식을 생각할 수 있다.

N 을 만드는 갯수 = (N-1 을 만드는 갯수+N-2 를 만드는 갯수+N-3 을 만드는 갯수) 로 하면 간단하다.

 

파이썬 코드는 다음과 같다.

저 d 배열은 dp 배열인데, 0,1,2,3인 경우의 수는 미리 초기화하였다.

import sys


a = int(sys.stdin.readline().rstrip())
d = [0,1,2,4]

for i in range(4,12):
    d.append(d[i-1]+d[i-2]+d[i-3]) 

for i in range(a):
    n = int(sys.stdin.readline().rstrip())
    print(d[n])