[Python] 백준(BOJ) 9095번: 1, 2, 3 더하기 - dp

문제

9095번: 1, 2, 3 더하기

풀이

규칙을 먼저 찾았다.

1 -> 1 (1)

2 -> 2 (1+1, 2)

3 -> 4 (1+1+1, 1+2, 2+1, 3)

4 -> 7 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2) 

 

배열로 정리하면 다음과 같다

i	1	2	3	4	5	6	7
arr[i]	1	2	4	arr[1]+arr[2]+arr[3]	arr[2]+arr[3]+arr[4]	arr[3]+arr[4]+arr[5]	arr[4]+arr[5]+arr[6]

그 후 최대 숫자가 11로 매우 작길래 11까지 배열을 미리 생성해두고 필요한 값만 출력했다. 

import sys

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

arr = []
for i in range(1, 12):
    if i == 1:
        arr.append(1)
    elif i == 2:
        arr.append(2)
    elif i == 3:
        arr.append(4)
    else:
        arr.append(arr[i-2]+arr[i-3]+arr[i-4])

for _ in range(TC):
    num = int(sys.stdin.readline())
    print(arr[num-1])