15988 1,2,3 더하기 3 _python

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

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

T의 범위가 주어져있지 않지만 상관없는 문제

 

 

 

문제 접근

1,2,3을 미리 적어두고 4부터 차근차근 개수를 새보면 점화식이 눈에 보인다.

5까지만 적었는데도 규칙이 바로 보였다.

1-> 1

2-> 2

3-> 4

4-> 7

5-> 13

까지만 적었는데 규칙이 보였다.

혹시모르니 7은 예시에 있길래 6까지 더 구했다.

6-> 24

7-> 44

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

이런 점화식을 얻을 수 있다.

 

이걸 이용해서 dp를 만들면 되는데

범위를 신경안쓰고 처음엔 이렇게 만들었다.

import sys
input = sys.stdin.readline

dp = [1,2,4] + [0]*999998
for i in range(3,1000001):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

T = int(input())
for i in range(T):
    print(dp[int(input())] % 1000000009)

메모리 초과.

 

 

당연 dp가 100만개의 배열이라서 초과하니까 입력받으면서 해당 범위까지만 dp를 축적하도록 append를 써야하나 했는데,

print에서 1000000009로 나누는게 비효율적이라서 메모리초과가 뜬다고 한다.

생각해보니 dp값을 나눠서 저장하지않으면 int범위를 넘어가버리는게 모두 추가메모리를 차지하게 되는거였다.

그래서 1000000009로 나눈값을 저장하도록 바꿨다.

 

 

 

코드

import sys
input = sys.stdin.readline

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

T = int(input())
for i in range(T):
    print(dp[int(input())])