[Python/파이썬] 백준 15990번 1, 2, 3 더하기 5

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

 

코드

dp = [[0]*3 for _ in range(100001)]  # 1열은 이번에 1 더했을 때, 2열은 2, 3열은 3 더했을 때
dp[1][0] = 1
dp[2][1] = 1
dp[3] = [1, 1, 1]
for i in range(4, 100001):
    dp[i][0] = (dp[i-1][1]+dp[i-1][2]) % 1_000_000_009
    dp[i][1] = (dp[i-2][0]+dp[i-2][2]) % 1_000_000_009
    dp[i][2] = (dp[i-3][0]+dp[i-3][1]) % 1_000_000_009

for _ in range(int(input())):
    n = int(input())
    print(sum(dp[n]) % 1_000_000_009)

 

DP 알고리즘으로 쉽게 풀 수 있는데, 같은 수를 연속해서 두 번 사용할 수 없다는 조건만 조심하면 된다.

같은 수를 2번 사용하는 것을 막기 위해 2차원 리스트 dp를 만들어서 dp[i][0]에는 숫자 i를 만들면서 마지막에 1을 더해서 만든 경우의 수, dp[i][1]은 마지막에 2를 더한 경우, dp[i][2]는 마지막에 3을 더한 경우의 수를 저장하면 된다.

 

다만, 이 문제에서 시간 초과가 발생하지 않으려면 dp를 매 테스트케이스마다 계산하면 안되고, 처음에 한번 10,000까지 다 계산해놓고 써야 한다.