[백준/Python] 15988번 - 1, 2, 3 더하기 3

import sys
input = sys.stdin.readline

DIV = 1000000009

dp = [1, 2, 4, 7]
for _ in range(int(input())):
  # 방법의 총 수 dp, 순서 바꾸는 것도 포함이네..
  n = int(input())

  for i in range(len(dp), n):
    # 알아서 1, 2, 3이 각각 들어갈 것 -> 겹치는게 없음
    dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % DIV)

  print(dp[n-1])

점화식은 발견 했는데 시간 초과, 메모리 초과를 어떻게 해결해야할지 생각해내는게 어려웠다.

이를 해결한 방법은 다음과 같다.

 

1. 모든 테스트케이스는 같은 DP 값을 가지니 DP를 global 하게 사용

2. 이미 있는 dp 값을 재활용하기 위해 for문 start가 len(dp)로 들어감

3. dp[3]까지 값을 미리 넣어놓기

+) 참고로 숫자는 그때 그때 나눠서 넣어야한다! DP 값에는 나머지 값이 들어가야한다는 의미!

 

 

시간 복잡도

n은 양수, 1,000,000 보다 작거나 같다

테스트 케이스가 몇개인지는 모르곘으나 한 테스트 케이스의 시간 복잡도는

for문: O(n)

=> O(n)