✍ 문제

문제링크: https://www.acmicpc.net/problem/1463

👏 풀이과정

가장 기본적인 dp로 푸는 문제이다. 다운업 방식을 이용해 주었다.
dp[1], dp[2], dp[3] 을 1로 초기화 시켜주고
dp[i + 1] = dp[i + 1] + dp[i]
dp[i + 2] = dp[i + 2] + dp[i]
dp[i + 3] = dp[i + 3] + dp[i]

이 방식을 사용하여 1부터 N+3까지 구해주었다.

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    dp = [0] * (N + 4)
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1

    for i in range(1, N + 1):
        dp[i + 1] = dp[i + 1] + dp[i]
        dp[i + 2] = dp[i + 2] + dp[i]
        dp[i + 3] = dp[i + 3] + dp[i]
    print(dp[N])