[BOJ] 1, 2, 3 더하기 3

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

 

1. 문제 이해 및 해결과정

 - 1,2,3 더하기 에서 범위가 바뀐 문제이다.

 - 중간에 %100000~9 를 안해주면 메모리 초과가 난다. 

 

2. 풀이방법

 1. DP

#1, 2, 3 더하기 3
#https://www.acmicpc.net/problem/15988
import sys
t=int(input())

for _ in range(t):
    n=int(input())
    dp=[0]*1000002
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    if n>=4:
        for i in range(4,n+1):
            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000009
    print(dp[n]%1000000009)

 2. DP 개선 코드 -시간 , 메모리 더 아낄 수 있음 

#1, 2, 3 더하기 3
#https://www.acmicpc.net/problem/15988
import sys
sys.stdin = open("input.txt","r")
t=int(input())
dp=[0,1,2,4]
for i in range(4, 1000000 + 1):
    dp.append((dp[i - 1] + dp[i - 2] + dp[i - 3])%1000000009)
for _ in range(t):
    n=int(input())
    print(dp[n]%1000000009)

 

3. 오답원인

- 코드중간에 %100~9를 안해주고 출력시에만 해줬더니 메모리 초과 -> 중간에도 해줄 것 

 

4. 알게된 점