백준 2294) 동전 2

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

2294번: 동전 2

 

문제

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

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

입력

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

출력

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

 

 

---

 

접근 방법

 

동전 1 문제에 다음과 같은 조건이 추가된 문제다.

1. 동전의 개수가 최소가 되도록

2. 사용한 동전의 최소 개수를 출력하기

 

 

우선 dp 관점에서 동전 2 문제를 푸는 방법을 살펴보자.

1) D[0]일 때는 값이 얼마일까?

합이 0이어야 하고, 최소 개수를 출력해야 하기 때문에 경우의 수는 0이다.

 

참고) 만약 최소 조건이 없다면?

D[0] = 1이어야 한다. 모든 경우의 수를 고려해야 하기 때문에 k = 1 이라면 D[1]에는 D[0]을 더한 값(0+1)이 저장되어야 한다.

그래야 올바르게 D[1]부터 저장될 수 있다.

 

2) 조건 1 : 최소가 되도록 한다.

우리가 찾고자 하는 동전의 합 k에 대해서, 1, 5, 12 의 동전이 있다고 가정한다.

 

k = 1이 될 때는,

1 -> 1개이다.

 

k = 2가 될 때는,

1 + 1 -> 1개이다.

 

...

 

k = 5가 될 때는,

1 + 1 + 1 + 1 + 1

5

-> 2개이다.

 

하지만 우리는 최소를 구해야 하기 때문에 1 + 1 + 1 + 1 + 1 을 제외해야 k=5 가 될 때 최소가 되는 것은 5 하나이므로

-> 1개이다.

 

3) 사용한 동전 구성은 같으나 순서만 다른 것은 같은 경우로 따져야 한다.

이를 구현하기 위해서는 1-K까지의 범위를 구하면서 동전들을 추가하지 말고, 동전들을 기준으로 1-K까지 더해준다.

 

1) 1-K 까지 범위를 구하면서 동전을 추가

 

1 = 1

2 = 1 + 1

3 = 1 + 1 + 1

...

5 = 1 + 1 + 1 + 1 + 1, 5

6 = 1 + 1 + 1 + 1 + 1 + 1, 1 + 5, 5 + 1

 

-> 순서가 뒤바뀔 수 있다.

 

 

2) 동전들을 기준으로 1-K까지 추가

 

동전 = 1일 때

1 = 1

2 = 1 + 1

3 = 1 + 1 + 1

...

5 = 1 + 1 + 1 + 1 + 1

6 = 1 + 1 + 1 + 1 + 1 + 1

 

동전=5일 때

1 = 1

2 = 1 + 1

3 = 1 + 1 + 1

...

5 = 1 + 1 + 1 + 1 + 1, 5

6 = 1 + 1 + 1 + 1 + 1 + 1, 1 + 5

 

->  동전의 순서는 크게 상관없지만, 1,5 순서라고 하면 1을 다 채운 후에 5를 채우게 되므로 순서를 항상 보장한다!

 

4) 점화식을 세워보자.

D[k] = 합이 k일 때의 최소의 동전 개수

D[k] = min(D[k], D[j-k] + 1) (j는 1-k까지일 때의 동전의 크기)

 

5) 마지막으로 동전의 개수를 셀 수 없는 경우를 고려하기

for(i in a) {
        for(j in 1..k) {
            if(j-i >= 0 && dp[j-i] != -1) {
                if(dp[j]== -1 || dp[j] > dp[j-i] + 1)
                    dp[j] = dp[j-i] + 1
            }
        }
    }

 

 

처음에 dp 배열 안에 -1 을 모두 저장시켰다.

dp[j-i] != -1 을 해준 이유는 만약 dp[j-i]에 아무것도 저장되지 않아 초기값 -1이 저장된 상태에서 경우의 수를 더해주는 것을 방지하는 역할을 나타내기 위함이다.

dp[j]== -1 || dp[j] > dp[j-i] + 1 조건은 최솟값을 찾게 한다. 

-1이 저장돼있으면 아직 최소 비교를 하지 않았으므로 그대로 넣고,

그것이 아니라면 최소 비교를 해준다.

 

 

소스 코드

 

fun main() = with(System.`in`.bufferedReader()) {
    val (n,k) = readLine().split(" ").map { it.toInt() }
    val a = IntArray(n)
    val dp = IntArray(10001) {-1}

    repeat(n) {
        a[it] = readLine().toInt()
    }

    dp[0] = 0
    for(i in a) {
        for(j in 1..k) {
            if(j-i >= 0 && dp[j-i] != -1) {
                if(dp[j]== -1 || dp[j] > dp[j-i] + 1)
                    dp[j] = dp[j-i] + 1
            }
        }
    }
    println(dp[k])
}