[Swift][DP] 백준 15988번 (1, 2, 3더하기 3)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

문제를 설명해주면 1과 2와 3중 한개 이상을 더해서 주어진 수를 만드는 문제이다.

처음 접해보시는 분들은 어렵게 느껴질 수도 있는데, 이 문제만 정확히 이해하면 다른 더하기 DP문제들은 꽤 쉽게 풀릴것이다.

 

그림을 보면 파란색글씨로 + 1, + 2, +3 을 해놓은것을 볼 수 있다.

1, 2, 3더하기니까 이렇게 1, 2, 3을 기준으로 앞에 들어와야 할 수를 구해준다.

이게 가능한건 DP이기 때문에 가능하다.

+1, +2, +3앞에 오는 수가 무엇이든간에 이미 1과 2와 3의 조합으로만 더해놨기 때문이다.

위의 그림에 5를 보면 이전에 4를 1과 2와 3의 조합으로 해놨기 때문에, 4에 조합된 개수를 그대로 가져오는걸 볼 수 있다.

이해가 안간다면 여러번보고 그래도 안가면 외우고 여러개 풀다보면 이해가간다.

 

후기 : 이전에 풀었던 1,2,3 문제들 보다는 훨씬쉬웠다.

let t = Int(String(readLine()!))!
var arr = [Int]()
var dp: [Int] = Array(repeating: 0, count: 1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in stride(from: 4, through: 1000000, by: 1) {
    dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009
}

for _ in 1...t {
    let a = Int(String(readLine()!))!
    print(dp[a])
}