[2294] 동전 2

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

2294번: 동전 2

직전에 풀었던 15988번 문제와 비슷하면서도 고민을 해봐야 하는 문제였다. 결국 다른 분의 풀이를 보고서 정답을 얻을 수 있었다.

 

풀이

배열 dp는 k개의 요소로 구성된 배열이며 dp[k]는 k원을 만들 수 있는 동전의 개수를 담고 있다.

dp[0]은 0원을 만들 수 있는 동전의 개수. 즉 0개부터 시작한다. 이후 동전을 담아놓은 배열을 순회하면서 dp를 갱신한다.

예제를 예시로 들겠다. 1원 5원 12원 동전이 있고, 목표 액수는 15원이다. 

우선 1원만 사용하여 dp배열을 갱신하면 아래와 같다.

0	0	0개
1	1	1개
2	1 + 1	2개
3	1 + 1 + 1	3개
4	1 + 1 + 1 + 1	4개
5	1 + 1 + 1 + 1 + 1	5개
...	...	...
15	1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1	15개

다음으로 5원을 사용하여 dp배열을 갱신하면 다음과 같다.

0	0	0개
...	...	...
5	5	1개
6	1 + 5	2개
7	1 + 1 + 5	3개
8	1 + 1 + 1 + 5	4개
9	1 + 1 + 1 + 1 + 5	5개
10	5 + 5	2개
11	1 + 5 + 5	3개

사용할 동전의 가치가 coin원이고, 목표금액이 k원이라면 dp 배열의 요소 dp[k]는 dp[k-coin]+1로 갱신이 가능하며, 이를 통해 더 작은 값으로 갱신해주면 된다. 

즉 coin번째 배열부터 시작하여 갱신을 시작하면 되며, dp[0] = 0 인 상태에서 점화식은 다음과 같이 세울 수 있다.

점화식

dp[k] = min( dp[k], dp[k-coin]+1 )

 

코드

import Foundation

let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
var k = nk[1]

var dp = Array(repeating:10001, count:10001)
dp[0] = 0
var coins = [Int]()
for _ in 0..<n{
    let coin = Int(readLine()!)!
    if coin <= 10000{ coins.append(coin) }
}
//coins = coins.sorted(by: <)

for coin in coins{
    for i in coin...10000{
        dp[i] = min(dp[i], dp[i-coin]+1)
    }
}
if dp[k] == 10001{
    print(-1)
}else{
    print(dp[k])
}

문제를 풀 당시 coins배열을 오름차순 정렬했는데, 풀이를 적다 보니 coin의 오름차순 정렬은 할 필요가 없다는 것을 깨달았다.