[파이썬(python)] 백준 15988

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

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

 

첫 코드

 

t = int(input())
n = []

for _ in range(t):
    n.append(int(input()))
    
max_n = max(n)
result = [0] * (max_n+1)
result[1] = 1
result[2] = 2
result[3] = 4


for i in range(4, max_n+1):
    result[i] = result[i-1] + result[i-2] + result[i-3]

for i in range(t):
    print(result[n[i]])

 

그 결과.. 메모리 초과 발생 ㅜㅜ

예제에 대해서는 맞았는데 무슨 문제인지 한참 들여다보다가

 

문제에서 10000009로 나눠줘야 한다는 것을 보고 그걸 반영해봤다.

그렇게 하니까 메모리 초과 안남!!! 성공.

아마도 배열에 10000009보다 큰 수가 들어가면 메모리 초과가 발생하는 것 같다.

 

t = int(input())
n = []

for _ in range(t):
    n.append(int(input()))
    
max_n = max(n)
result = [0] * (max_n+1)
result[1] = 1
result[2] = 2
result[3] = 4


for i in range(4, max_n+1):
    result[i] = (result[i-1] + result[i-2] + result[i-3])%1000000009

for i in range(t):
    print(result[n[i]])