728x90
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
코드
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식] 의 형태로 나누어지는 것이다.
'알고리즘 풀기' 카테고리의 다른 글
BOJ 2133 타일 채우기 (0) | 2020.10.28 |
---|---|
BOJ 1088 쉬운 계단 수 python3 (0) | 2020.04.17 |
BOJ 1149 RGB거리 python3 (0) | 2020.04.17 |
[백준] 1759 암호 만들기 python3 (0) | 2020.03.18 |