BOJ-2294 동전 2 Swift

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

내가 푼 풀이

- k원이 되도록 n가지 동전의 개수가 최소가 되게끔 한다.

- 기본적으로 k원이 될때, n가지 동전 중 가치가 높은 동전을 최대한 많이 사용하면 개수가 최소가 된다.

- dp [n] = n원이 되도록 하는 동전의 최소개수 라 정의하자.

- 예제 입력을 통해 어떻게 코드로 구현했는지 보자.

 

n = 3, k = 15, [1,5,12] : 3가지의 동전으로 15원을 만드는 동전의 최소개수는?

위의  입력이 주어졌을 때, 동전을 한번 사용하는 경우 : dp[1] = 1 , dp[5] = 1, dp[12] = 1 이 된다.

dp	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
dp[n]	1	2	3	4	1							1

- 2원: 1원 + 1원  -> dp[2] = dp[1] + 1

- 3원: 2원 + 1원  -> dp[3] = dp[2] + 1

- 4원: 3원 + 1원  -> dp[4] = dp[3] + 1

- 5원: 4원 + 1원,  5원 dp[5] = min(dp[0] + 1 , dp[4] + 1)

5원을 만들 수 있는 경우의 수 중 최솟값을 저장한다. 

dp	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
dp[n]	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

dp[n] 은 n원을 만드는 최소 동전개수이므로 1원 6개를 만드는 경우는 배제하고, 6원을 만드는 최적의 방법만 검사한다.

- 6원: 5원 + 1원 : dp[6] = dp[5] + 1

- 10원: 5원 2개,  9원 + 1원 : min( dp[5] + 1 , dp[9] + 1 )

 

위와 같이 n원을 만들 때, 사용 가능한 동전들의 경우의 수들 중 최솟값을 저장한다.

코드로 구현하면 다음과 같다.

 

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Int]()
var dp = Array(repeating: 0, count: input[1]+1)
dp[0] = 0

// n가지 동전의 종류를 배열로 입력
for i in 0..<input[0] {
    var num = Int(readLine()!)!
    arr.append(num)
}

// DP 입력
// dp[n] = n원을 만드는 최소 동전 개수
for i in 1...input[1] {
    var a = [Int]()
    // 해당 동전을 사용할 수 있는지 확인한다.
    // 주어진 동전들을 이용해서 만들수 있는지 확인: dp[i-arr[j]] != -1
    for j in 0..<arr.count {
        if i - arr[j] >= 0 && dp[i-arr[j]] != -1 {
            a.append(dp[i-arr[j]] + 1)
        }
    }
    // 만들 수 없다면 -1
    // 만들 수 있다면 만드는 경우의 수 중 최솟값을 저장
    if a.isEmpty {
        dp[i] = -1
    } else {
        dp[i] = a.min()!
    }
}
print(dp[input[1]])