greentea31's Note

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

풀이 과정

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 d[n]이라고 하자

n-3을 나타내는 1, 2, 3의 합으로 이루어진 식에 +3을 해주면 정수 n을 나타내고,

n-2을 나타내는 1, 2, 3의 합으로 이루어진 식에 +2을 해주면 정수 n을 나타내고,

n-1을 나타내는 1, 2, 3의 합으로 이루어진 식에 +1을 해주면 정수 n을 나타낸다

따라서, d[n] = d[n-3] + d[n-2] + d[n-1]이라는 점화식이 성립한다 

소스 코드

import sys
T = int(sys.stdin.readline())

for _ in range(T):
    n = int(input())
    d = [0, 1, 2, 4]
    for i in range(4, n+1):
        d.append(d[i-1] + d[i-2] + d[i-3])
    print(d[n])