[BOJ/백준] 9095 - 1, 2, 3 더하기 (Python)

문제

문제링크

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라.

 

풀이

n=1일 경우 1, n=2일 경우 1+1와 2, n=3일 경우 1+1+1와 1+2와 2+1와 3가 가능하다.

마지막에 3을 더하는 경우는 n-3까지를 나타내는 방법의 수와 같으므로 dp[n-3]와 같다.

2를 더하는 경우는 dp[n-2], 1을 더하는 경우는 dp[n-1]와 같다.

dp[n]은 이 세 경우 모두 포함하므로 dp[n]=dp[n-3]+dp[n-2]+dp[n-1]이다.

 

코드

import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    dp=[0]*(n+1)

    dp[1]=1
    if n>=2:
        dp[2]=2
    if n>=3:
        dp[3]=4
    for i in range(4,n+1):
        dp[i]=dp[i-3]+dp[i-2]+dp[i-1]
    print(dp[n])