[백준] 15988번 : 1, 2, 3 더하기 3 (python 파이썬)

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

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

 

 

 

 

 

문제 정리 : 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수 출력.

import sys



l = [0 for k in range(1000001)] # 미리 n의 최대 범위까지의 답을 만든다.
l[0] = 1 # 1인 경우 ([1])
l[1] = 2 # 2인 경우 ([1,1] ,[2])
l[2] = 4 # 3인 경우 ([1,1,1],[1,2],[2,1],[3])
for j in range(3,1000001): 4 부터 n의 최대 범위 까지

    l[j] = l[j-1]% 1000000009+l[j-2]% 1000000009+l[j-3]% 1000000009
        
m = int(sys.stdin.readline()) # 테스트 케이스의 개수 

for i in range(m): 
    n = int(sys.stdin.readline()) # n 입력 받기
    print(l[n-1]% 1000000009) # 정답 출력

 

간단한 dp 문제이다. n = 1, 2 ,3 인 경우를 미리 만든 후 4 부터는 n-1, n-2, n-3 인 경우의 수의 합을 집어넣는다.

사용할 수 있는 수는 1,2,3 뿐이기 때문에 n의 경우로 올 수 있는 경로는 (n-3 => n) (n-2=>n) (n-1=>n) 세 가지이다.

따라서 미리 구해놓은 각각의 경우에 3, 2, 1을 추가로 더한 경우를 합한 경우의 수가 n의 경우의 수가 된다.

 

또한 dp 문제를 푼다 해도, 각각의 테스트 케이스마다 처음부터 수행하게 되면, 시간오류가 발생하게 된다.

미리 구해놓은 경우의 수를 다시 지우고 다시 구하는 과정을 t번 반복하게 되면 필요없는 계산이 많이 발생하기 때문이다.

따라서 미리 n의 최대 범위까지의 범위의 값을 구해놓고, t번 반복하면서 답만 출력하는 과정을 통해 시간을 절약할 수 있다.