[백준] 1, 2, 3 더하기 4

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

15989번: 1, 2, 3 더하기 4

 

숫자 1 만으로 나타내는 방법은 각각 1가지가 있다. dp[i] = 1

다음 2 를 사용해도 된다고 하면 dp[2] = 2 이다. ((1, 1), (2)), dp[3] = 2 이다. ((1, 1, 1), (2, 1))

dp[4] 는 원래 (1, 1, 1, 1) 과 dp[4-2] 인 경우 (1, 1), (2) 에 2를 넣으면 되기 때문에((1, 1, 2), (2, 2)) dp[4] = dp[4] + dp[2] = 3 이 된다. 즉, dp[i] += dp[i-2]

 

다음 3 을 사용해도 된다고 하면 같은 원리로 dp[i] += dp[i-3] 으로 dp 배열을 완성할 수 있다.

 

import sys

T = int(sys.stdin.readline())
dp = [1] * 10001

for i in range(2, 10001):
    dp[i] += dp[i - 2]
    
for i in range(3, 10001):
    dp[i] += dp[i - 3]
    
for i in range(T):
    n = int(sys.stdin.readline())
    print(dp[n])