[파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3)

[파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3)

 

9095번: 1, 2, 3 더하기

---

문제

---

풀이

방향성 생각

DP 문제이므로 초기 값들 몇개를 찾아서 규칙을 찾는다

규칙을 찾아보면 최근에 나온 3가지 수를 모두 더하면 다음 경우의 수가 나오는 것을 확인할 수 있다.

5 -> 13, 6->24

어떤 자연수 n을 만들 때 1 2 3으로만 만든다고 했으므로 1+(n-1), 2+(n-2), 3+(n-3), 뒤에 나오는 경우의 수들은 앞에서 이미 구한 값들을 통해서 구할 수 있다. 

an = [0,1,2,4]
for i in range(9):
    an.append(sum(an[-3:]))
t = int(input())
for i in range(t):
    n = int(input())
    print(an[n])