[백준/파이썬] 9095번: 1, 2, 3 더하기

문제

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

풀이

먼저 문제를 접했을 때 점화식부터 구해봤습니다.

f(1) = 1 = 1
f(2) = 1+1, 2 = 2
f(3) = 1+1+1, 1+2, 2+1, 3 = 4
f(4) = 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 = 7
f(5) = 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2 = 13
f(6) = 1+1+1+1+1+1, 1+1+1+1+2(5), 1+1+2+2(6), 2+2+2, 1+1+1+3(4), 1+2+3(6), 3+3 = 24

규칙이 생기는 것이 보이시나요?
f(4)를 보게 되면 f(1)+f(2)+f(3)의 값이고, f(5)는 f(4)+f(3)+f(2)의 값인 것을 확인할 수 있습니다.
이를 이용해 코드를 작성하면 문제를 쉽게 해결할 수 있습니다.

코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    dp = [0] * (n+1)
    dp[1:4] = 1, 2, 4 # f(1), f(2), f(3)의 값은 저장
    if dp[n] == 0: # 구하려는 값이 dp에 저장되어 있지 않은 경우
        for i in range(4, n+1):
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[n])