BOJ 15990 1, 2, 3 더하기 5

www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

코드

from sys import stdin
input = stdin.readline

MOD = 1000000009
T = int(input())
dp = [[0, 0, 0] for _ in range(100001)]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]
dp[4] = [2, 0, 1]

for i in range(5, len(dp)):
    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % MOD
    dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % MOD
    dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % MOD

for _ in range(T):
    print(sum(dp[int(input())]) % MOD)

 

해설

이러한 순서쌍이 있다고 할 때, 총합이 5인 배열들은 다음과 같이 나타낼 수 있다.

 

 

이를 일반화 하면 다음과 같다.

 

 

다음의 예처럼, [숫자블럭] [이전 dp식] 의 형태로 나누어지는 것이다.