[Baekjoon] DP - 15988 1, 2, 3 더하기 3

ddu0422 2023. 9. 25. 11:56

문제

15988번: 1, 2, 3 더하기 3

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

www.acmicpc.net

풀이

import sys

MOD = 1000000009

t = int(sys.stdin.readline().rstrip())
d = [0] * 1000001
result = []


def solution(n):
    if n <= 2:
        return n

    d[1] = 1
    d[2] = 2
    d[3] = 4

    for i in range(4, n + 1):
        d[i] = (d[i - 1] + d[i - 2] + d[i - 3]) % MOD

    return d[n] % MOD


for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    result.append(solution(n))


print(*result, sep='\n')

채점 결과

저작자표시 (새창열림)