백준|9095번|1,2,3 더하기

문제설명
입력받은 정수를 1,2,3의 조합으로 나타낼수 있는 방법의 수를 출력하는 문제입니다.

작동 순서
1. 각 정수를 나타낼 수 있는 조합의 개수는 (n-1)의 조합의 개수+(n-2)의 조합의 개수+(n-3)의 조합의 개수이므로 모두 구해줍니다.
2. 입력받은 정수를 나타낼 수 있는 조합의 개수를 출력합니다.

소스코드

import sys
T = int(sys.stdin.readline())
arr = [0, 1, 2, 4]+[0]*8
for i in range(4, len(arr)):
    arr[i] = arr[i-3]+arr[i-2]+arr[i-1]
for i in range(T):
    n = int(sys.stdin.readline())
    print(arr[n])

후기
처음볼때는 복잡해보였는데 수들의 규칙을 이해하고 나니 쉽게 풀 수 있었습니다. DP문제는 구현은 복잡하지않은데 점화식을 세우는게 어려운것 같습니다.