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

나의 코드

import sys
input = sys.stdin.readline

T=int(input())
dp=[[0,0,0] for _ in range(10001)]
dp[1]=[1,0,0]
dp[2]=[1,1,0]
dp[3]=[1,1,1]
last=4
for _ in range(T):
    n=int(input())
    for i in range(4,n+1):
        dp[i]=[dp[i-1][0],dp[i-2][0]+dp[i-2][1],dp[i-3][0]+dp[i-3][1]+dp[i-3][2]]
    
    print(sum(dp[n]))
    last=n+1

수행시간: 184ms(pypy3)

나의 풀이

dp에는 정수i를 1,2,3의 합으로 나타내는 구성을 [1이 가장 큰 구성, 2가 가장 큰 구성,3이 가장 큰 구성] 로 저장한다.

dp[i]의 1이 가장 큰 구성은 dp[i-3]의 1이 가장 큰 구성과 같다.
dp[i]의 2가 가장 큰 구성은 dp[i-2]의 1이 가장 큰 구성과 2가 가장 큰 구성의 합 과 같다.
dp[i]의 3가 가장 큰 구성은 dp[i-1]의 모든 구성의 합과 같다.

다른 코드

import sys
input = sys.stdin.readline

T=int(input())
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 _ in range(T):
    print(dp[int(input())])

수행시간: 72ms(python3)

풀이

정수 i를 1,2,3의 합으로 나타내는 구성을 1이 가장 큰 값일 때의 구성을 구하고, 2가 가장 큰 값일 때의 구성을 구하고, 3이 가장 큰 값일 때의 구성을 구하는 방식으로 풀었다.

1이 가장 큰 값인 구성은 무조건 1개이므로 dp값들을 처음부터 1로 설정하였다.
2가 가장 큰 값인 구성은dp[i]에다가 dp[i-2]를 더하면 된다.
3도 마찬가지로 dp[i]+=dp[i-3]을 해주면 된다.
위 순서대로 dp[i]값을 업데이트 해줘야 3이 가장 큰 값인 구성이 2가 가장 큰 값인 구성에 영향을 끼치지 않는다.