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로 나눈 나머지 저장 (분배법칙 적용)
'algorithm > DP' 카테고리의 다른 글
[백준22115/골드5] 창영이와 커피 - Python (0) | 2025.02.10 |
---|---|
[백준11057/실버1] 오르막 수 - Python (0) | 2025.02.04 |
[백준11909/골드5] 배열 탈출 - Python (0) | 2025.01.26 |
Dynamic Programming 동적계획법 (0) | 2025.01.14 |
[백준15989/골5] 1, 2, 3 더하기 4 - Python (0) | 2025.01.06 |