[백준]BOJ 2293 - 동전 1 - Swift/DP

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

2293번: 동전 1

문제

풀이

DP를 사용하는 문제이다. dp 테이블의 각 인덱스가 해당 인덱스 만큼의 가치를 만들 수 있는 경우의 수 라고 하면 쉽게 풀 수 있다.

 

동전의 가치를 value라고 하면 그 동전을 하나 추가해서 i만큼의 가치를 만들 수 있는 경우의 수는 dp[i] += dp[i - value] 라고 할 수 있다.  따라서 하나의 가치에 대해서 동전의 종류의 수 만큼 반복문을 돌려야 한다.

 

문제에서 주어진 또 다른 조건은 경우의 수가 2의 31승이 넘지 않는다는 것이다. 또한 스위프트에서는 오버플로우를 방지하기 위해 2의 31승이 넘어가는 수를 다 제거해줘야 한다. (최종적으로 출력할 결과가 2의 31승이 넘어가지 않으므로 중간에 2의 31승이 넘는 값은 자연스럽게 쓸모가 없는 값이 된다.)

코드

import Foundation

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, k) = (nk[0], nk[1])
var values: [Int] = []
for _ in 0..<n {
    values.append(Int(readLine()!)!)
}
var dp = [Int](repeating: 0, count: k + 1)
dp[0] = 1
for value in values {
    if k >= value {
        for idx in value...k {
            dp[idx] += dp[idx - value]
            if dp[idx] >= 2_147_483_648 {
                dp[idx] = 0
            }
        }
    }
}
print(dp[k])