[BOJ]15988 - 1, 2, 3 더하기 3 (Python)

문제 

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

코드 

import sys
input = lambda : sys.stdin.readline().strip()

n = int(input())
dp = [0] * 1000001
dp[1], dp[2], dp[3] = 1, 2, 4
for i in range(4, 1000001):
    dp[i] = dp[i - 1] % 1000000009 + dp[i - 2] % 1000000009 + dp[i - 3] % 1000000009

for _ in range(n):
    num = int(input())
    print(dp[num] % 1000000009)

 

풀이

1번째는 메모리 초과, 2번째 시도는 시간초과로 틀린 문제이다 

메모리 초과는 왜 나는지 계속 찾아보았는데 스택에 저장되는 수가 너무 커서 생기는 문제였다

dp[i] = dp[i - 1]  + dp[i - 2]  + dp[i - 3]

위의 코드처럼 처음에는 그냥 다 저장했는데 생각해보니 답을 1000000009로 나누라는 말이 괜히 있는게 아닌거 같아서 리스트 내의 수를 넣을 때부터 1000000009로 나눈 나머지를 저장하였더니 메모리 초과는 나지 않았다 

 

이제 시간초과가 났다ㅋㅋㅋㅋ

내 원래 코드는 하나의 수를 입력받을 때마다 리스트를 새로 만들었다 

for _ in range(n):
    num = int(input())
    for i in range(4, num + 1):
        if dp[i] != 0:
            continue
        dp[i] = dp[i - 1]% 1000000009 + dp[i - 2]% 1000000009 + dp[i - 3]% 1000000009
    print(dp[num] % 1000000009)

위와 같이 생긴 코드였다 

근데 생각해보니까 리스트를 매번 만들 필요가 없고 처음부터 만들어 놓고 값만 가져다가 써도 풀 수 있는 문제길래 코드 초반에 미리 리스트를 만드니 시간초과도 뜨지 않았다 

 

Bottom up 방식으로 풀었는데 다음에는 top down으로도 풀어봐야겠다