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

초고

import sys
max = 10
sum = [0] * (max+1)
sum[0] = 0
sum[1] = 1
sum[2] = 2
sum[3] = 4
ans=[]
for i in range(4,max+1):
    sum[i] += sum[i-1] + sum[i-2] +sum[i-3]

t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    ans.append(sum[n])
for i in ans:
    print(i)

보자마자 dp 라는건 눈치 챘지만 문제 설명이 살짝 이해가 안되서 애를 먹었다..

• 1,2,3은 자기 자신도 합으로 갖는다!

시간복잡도

• O(max)

다른 사람의 풀이

import sys

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

for _ in range(data):
    num = []
    num.append(1)
    num.append(1)
    num.append(2)
    num.append(4)
    n = int(sys.stdin.readline())
    for i in range(4, n + 1):
        num.append(num[i - 1] + num[i - 2] + num[i - 3])

    print(num[n])

같은 효율성의 풀이지만 너무 깔끔하다..