[백준] 2294 동전 2

문제

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

 

입력

n = 동전의 종류 (1~100)
k = 목표 금액 (1~10,000)

coins = 각 동전 금액

결과

ans = k금액을 만들기위해 사용한 동전의 최소 개수. 불가능한 경우에는 -1

해석

이전에 풀었던 동전1 문제를 최소 개수 구하는 점화식으로 바꾸면 끝

dp[i] = i 금액을 만들기위해 사용한 최소 개수

 

코드

import Foundation

let nk = readLine()!.components(separatedBy: " ").map{Int($0)!}
let (n, k) = (nk[0], nk[1])

var coins: [Int] = []

for _ in 0..<n {
    coins.append(Int(readLine()!)!)
}

let MAX = 1000_1000

var dp: [Int] = [Int](repeating: -1, count: k+1)

dp[0] = 0

for coin in coins {

    if coin > k { continue }
    
    for i in 0...k-coin {
        if dp[i] == -1 { continue } // i원이 이전에 만든 적이 없으면 i+coin도 당연히 만들 수 없음
        if dp[i+coin] == -1 { // 처음으로 만들 때
            dp[i+coin] = dp[i]+1
        } else {
            dp[i+coin] = min(dp[i+coin], dp[i]+1) // 이후는 최소 값으로
        }
      
    }
}


print(dp[k])