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

문제

점화식 도출하기

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

우리가 구하고자 하는 것은 N을 1, 2, 3의 합으로 나타내는 방법의 수이다.

따라서 N을 만들기 위해서는 N-1을 만드는 방법, N-2를 만드는 방법, N-3을 만드는 방법을 합치는 것으로 생각할 수 있다.

따라서 점화식은 다음과 같이 나타낼 수 있다.

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

여기서 DP[N]은 N을 만드는 방법의 수를 나타내는 배열이며, DP[1], DP[2], DP[3]은 초기값으로 주어진다.

DP[1]은 1을 만드는 방법의 수인 1, DP[2]는 2를 만드는 방법의 수인 2, DP[3]은 3을 만드는 방법의 수인 4이다.

풀이

해당 문제를 풀이하면서 처음에 작성한 코드는 시간 초과 에러가 발생하였다.

# 코드는 맞지만, 시간 초과 발생 
def count_ways(n):
    dp = [0] * (n+1) # dp 리스트 초기화 
    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]) % 1000000009
    
    return dp[n]


t = int(input())
results = []

for _ in range(t):
    n=int(input())
    result = count_ways(n)
    results.append(result)

for i in results:
    print(i)

이렇게 시간 초과가 발생할 때는

1. 반복문을 사용하여 다이나믹 프로그래밍 구현:
   재귀 호출이 아닌 반복문을 사용하여 다이나믹 프로그래밍을 구현하면 중복 계산을 효율적으로 제거할 수 있다.

2. 공간 복잡도 최적화:
   문제에서 요구하는 것은 n을 1, 2, 3의 합으로 나타내는 방법의 수이므로, 모든 n에 대한 값을 저장할 필요는 없다.
   현재 값과 그에 필요한 이전 값만을 저장하여 공간을 절약할 수 있다.

3. 메모이제이션 활용

다음의 방법을 활용할 수 있다.

정답 코드

import sys

n = int(input())
arr = [0 for j in range(1000001)]
arr[0] = 1
arr[1] = 1
arr[2] = 2
for i in range(3, 1000001):
    arr[i] = arr[i - 1] % 1000000009 + arr[i - 2] % 1000000009 + arr[i - 3] % 1000000009
for i in range(n):
    a = int(input())
    # 이렇게 중복하여 나누는 이유는, 연산 과정에서 결과 값이 매우 커지는 것을 방지하기 위함. 
    # 합의 결과가 매우 커질 수 있으며, 연산 과정에서 오버플로우를 방지하기 위해 연산할 때마다 1000000009로 나누어 나머지 값을 적용
    print(arr[a] % 1000000009)