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

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

15988번: 1, 2, 3 더하기 3

대표적인 동적 계획법 문제이다. 동적 계획법은 항상 마주할 때마다 느끼듯이 점화식을 고민하는 데에 너무 오랜 시간이 걸린다. 더 많은 문제들을 풀어봐야 하나 보다.

 

풀이

정답을 표현할 배열 dp는 n+1개의 요소를 가지는 배열이며, dp[n]은 "1,2,3을 사용하여 n을 만들 수 있는 식의 개수"라고 정의한다.

점화식을 사용하기 위해서 배열에 최소 3개의 요소가 담겨있어야 한다. 1부터 3까지의 경우의 수를 적어보면 다음과 같다.

 

n	식의 종류
0	표현 불가능(입력범위 아님)
1	1
2	1+1, 2
3	1+1+1, 2+1, 1+2, 3

이후 1,2,3을 이용해 4를 만드는 식을 만든다고 가정할 경우, 다음과 같은 생각을 해볼 수 있다.

1. 1을 만들 수 있는 모든 식에 "+3"을 추가한다면 4를 만들 수 있다.
2. 2를 만들 수 있는 모든 식에 "+2"를 추가한다면 4를 만들 수 있다.
3. 3을 만들 수 있는 모든 식에 "+1"을 추가한다면 4를 만들 수 있다.

따라서 다음과 같은 점화식을 세울수있게된다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

다만 문제를 보면 알 수 있듯이 n의 크기가 1,000,000이므로 정답을 출력할 때 1,000,000,009로 나눈 나머지를 출력하라고 적혀있다.

모듈러 산술 연산법칙은 분배 법칙이 성립하므로 코드를 적을 때는 다음과 같이 적는다.

 

dp[n] = ((dp[n-1]%1,000,000,009) + (dp[n-2]%1,000,000,009) + (dp[n-3]%1,000,000,009))%1,000,000,009

 

정답 코드

import Foundation

var dp = Array(repeating: 0, count: 1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4
let mod = 1000000009

for i in 4...1000000{
    dp[i] = ((dp[i-1]%mod) + (dp[i-2]%mod) + (dp[i-3]%mod))%mod
}

for _ in 0..<Int(readLine()!)!{
    let n = Int(readLine()!)!
    print(dp[n])
}