greentea31's Note

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

풀이 과정

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

이 문제와 푸는 방법이 동일하나 들어올 수 있는 입력 n의 최대값이 11에서 10억 9라는 큰 숫자로 늘었다. 나머지 연산을 통해 오버플로우의 발생을 방지해야 한다.

(A+B+C) % M = ((A%M) + (B%M) + (C%M)) % M임을 이용해 계산 도중 숫자가 너무 커지지 않게 나머지 연산 처리를 적절히 끊어서 해주면 된다. 단 그래도 10억이 3번 더해지는 경우가 생길 수 있고, 이 경우에 int형 타입의 최대값인 2,147,483,647을 넘을수도 있으므로 unsigned int형태로 문제를 푸는 것이 좋지만 이건 c++등의 타 언어에서 고려해야 할 사항이고 파이썬에서는 그냥 int가 아주 큰 수도 처리할 수 있으므로 그냥 점화식을 통해 문제를 해결하면 된다.

d[i]를 정수 i를 1, 2, 3의 합으로 나타내는 경우의 수라고 하면

d[i] = d[i-1] + d[i-2] + d[i-3]이 성립한다.

소스 코드

import sys

mod = 1000000009
maximum_range = 1000001

T = int(sys.stdin.readline())
d = [0, 1, 2, 4]

for i in range(4, maximum_range):
    d.append(d[i-1] + d[i-2] + d[i-3])
    d[i] %= mod

for i in range(T):
    n = int(sys.stdin.readline())
    print(d[n])