[BOJ] 15988번: 1, 2, 3 더하기 3 (DP, 메모리 주의)

 

문제 링크

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

 

 

 

TIL

• 그냥 주어진 범위 그대로 배열을 초기화해서 사용하면 메모리 초과 뜸
• N의 범위가 크길래 Top-down으로 구현하려고 함
  • 시간초과 발생
  • testcase 의 max값을 구했다면 bottom-up도 가능
  • 추가로 1초 제한인데 최대가 1,000,000(100만)이기 때문에 bottom-up으로 해도 O(N)으로 1초 충분히 가능

 

 

 

Code

T = int(input())
testcase = []
for i in range(T):
    testcase.append(int(input()))

MOD = 1_000_000_009
end = max(testcase)

dp = [0]*(end+1)
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, end+1):
    dp[i] += ((dp[i-1] + dp[i-2] + dp[i-3]) % MOD)

for t in testcase:
    print(dp[t])