[Python] 백준 15988_1, 2, 3 더하기 3

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• d[i] = i를 1,2,3으로 만들 수 있는 가짓수
• d[0] = 0, d[1] = 1, d[2] = 2, d[3] = 4 으로 초기화
  

2. 점화식 찾기

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

3. 코드

n은 양수이며 1,000,000보다 작거나 같으므로 dp테이블을 d=[0]*1000001로 세팅해준다.
여기서 주의할 점은 테스트케이스를 돌리는 for문안에서 dp를 계산해주면 반복되는 계산을 계속 하게되므로 메모리 초과가 발생한다.(맨 마지막에 그렇게 구현해서 틀린 코드도 추가해두었다.)
따라서 테스트케이스를 돌리기 전에 미리 한번 n의 최대값까지 계산해줘야 한다. 그럼 메모리초과가 발생하지 않는다.

<맞은 코드>

import sys
input  = sys.stdin.readline

#dp정의
d = [0]*(1000000+1)
for i in range(1,1000000+1):
    if i==1:
        d[1]=1
    elif i==2:
        d[2]=2
    elif i==3:
        d[3]=4
    else:
        d[i] = (d[i-1]+d[i-2]+d[i-3])%1000000009
        
for t in range(int(input())):
    n = int(input())
    print(d[n])

<틀린 코드 - 메모리초과>

import sys
input  = sys.stdin.readline
result=[]
for t in range(int(input())):
    n = int(input())

    #dp정의
    d = [0]*(n+1)
    d[1]=1
    d[2]=2
    d[3]=4

    for i in range(4,n+1):
        d[i] = (d[i-1])+(d[i-2])+(d[i-3])
        
    result.append(d[n]%1000000009)

for x in result:
    print(x)