백준: 15988 1, 2, 3 더하기 3

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

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

 

문제 풀이

기존의 풀이 중 1, 2, 3 더하기와 같은 방식으로 규칙을 찾으면 n을 1, 2, 3을 더해나타낼 수 있는 경우의 수를 찾을 수 있다. 기존의 1, 2, 3 더하기 문제는 n의 범위도 작을 뿐더러 나누기 연산이 없었지만 이 문제는 범위가 1000000이다. 따라서 테스트 케이스 마다 n에 따른 경우의 수를 계산하는 것이 아니라, 미리 경우의 수를 계산해 두어야 시간 초과가 발생하지 않는다.

 

코드

from sys import stdin

if __name__ == '__main__':
    memo = [0] * 1000000
    memo[0], memo[1], memo[2] = 1, 2, 4

    for i in range(3, 1000000):
        memo[i] = (memo[i - 3] + memo[i - 2] + memo[i - 1]) % 1000000009

    for _ in range(int(stdin.readline())):
        n = int(stdin.readline())
        print(memo[n - 1])