[백준15989/실2] 1, 2, 3더하기 3 - Python

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

 

 

 

1, 2, 3 더하기 4가 스터디 문제로 나와서 3도 풀어봤다.

 

순서 없는 1, 2, 3 배열 수 구하는 문제라 점화식을 간단하게

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 으로 세웠는데 메모리 초과에 시간초과까지 완전 난리났다.

 

 

실패 코드
원인 1. 매 테스트케이스마다 dp 새로 계산 (시간초과)
원인 2. dp 테이블 저장할 때 1000000009로 나눈 나머지 저장 안 함 (메모리초과) -> 분배법칙 적용해서 해결..

for tc in range(int(input())):

    n = int(input())
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

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

    print(dp[n] % 1000000009)

 

 

 

성공 코드

# 1 : 1가지 (1)
# 2 : 2가지 (2, 1+1)
# 3 : 4가지 (3, 2+1, 1+2, 1+1+1)

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

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

for _ in range(int(input())):
    n = int(input())
    print(dp[n] % 1000000009)

 

1. n이 최대 1000000이므로 처음부터 다 저장하고 테스트 케이스만큼 하나씩 저장하는 방식으로 변경

2. dp 테이블에 값을 1000000009로 나눈 나머지 저장 (분배법칙 적용)