[백준 BOJ][DP] 2294 동전 2

2294_동전 2

 

링크

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

 

풀이

 

위 문제의 예제로 어떻게 풀어낼 수 있을 지 생각해 봅시다.

일단 0을 제외한 모든 배열의 인덱스를 10001로 초기화 해야합니다. 왜냐하면 최솟값을 구하는 문제이기 때문이죠. 그래서 나올 수 있는 최댓값보다 더 큰 값으로 초기화 했습니다(불가능한 경우까지 고려).

 

 

이제부터 1원을 이용해서 값을 만들어 봅시다.

1원을 만들려면, DP[1]과 DP[1-1]에 1원을 더하는 경우를 비교해야 합니다.

DP[1]은 초기값 10001이고, DP[1-1]에 1원을 더하는 경우는 DP[0] + 1이기 때문에 1입니다.

1이 더 작기 때문에 DP[1] = DP[0] + 1로 채택합니다.

 

2원을 만들겠습니다. 원래 DP[2]는 10001이고, DP[2-1] + 1은 2입니다. (DP[1] = 1)

때문에 DP[2] = DP[1] + 1입니다.

 

쭉 15원까지 만들면 이렇게 값을 가지고 있게 됩니다.

 

다음은 5원으로 만들어 봅시다.

5원을 가지고 5원 미만의 가치를 만들어내지 못 하기 때문에 5원부터 보겠습니다.

 

5원을 만들려면, DP[5]와 DP[5-5]에 5원을 더하는 경우를 비교해야 합니다.

DP[5]는 5이고, DP[5-5] + 1은 1입니다. 때문에 DP[5] = DP[0] + 1로 채택합니다.

6원을 만들려면, DP[6]과 DP[6-5]에 5원을 더하는 경우를 비교해야 합니다.

DP[6]은 6이고, DP[6-5] + 1은 2입니다. 때문에 DP[6] = DP[1] + 1로 채택합니다.

 

15원까지 하고 나면 이렇게 값을 가지고 있게 됩니다.

 

다음은 12원으로 만들겠습니다.

12원을 만들려면 DP[12]와 DP[12-12]에 12원을 더하는 경우를 비교해야 합니다.

DP[12]는 4이고, DP[12-12] + 1은 1입니다. 때문에 DP[12] = DP[0] + 1로 채택합니다.

 

이번에는 15원을 만들어볼까요?

DP[15]와 DP[15-12]에 12원을 더하는 경우를 비교합니다.

DP[15]는 3이고, DP[15-12] + 1은 DP[3] + 1이고 3 + 1 = 4입니다.

DP[15]가 더 작기 때문에 DP[15]는 그대로 DP[15]로 둡니다.

 

이렇게 하고 나면 이렇게 값을 가지고 있게 됩니다.

 

결국 15원을 만들 수 있는 최소 동전의 개수가 남게 됩니다.

이제 일반화를 시켜 봅시다.

 

n가지 동전을 담을 coin[101]과 합 DP[10001]을 만들어 줍니다.

i를 1~n(동전의 종류)까지 j를 coin[i]에서 k(가치의 합)까지 돌려줍니다.

그리고 j원을 만들려고 할 때, DP[j]와 DP[j-coin[i]]에 coin[j]를 추가했을 때를 비교해서 더 적은 동전을 사용했을 때를 채택해주면 됩니다.

 

DP[j] = MIN(DP[j], DP[j – coin[i]] + 1)

이렇게 점화식을 세울 수 있습니다.

 

마지막에 DP[k]가 10001이면 불가능한 경우이니 -1을 출력하면 됩니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

//2294_동전 2 #include <iostream> using namespace std;   int MIN(int a, int b) {     return a < b ? a : b; }   int main() {     int DP[10001] = { 0, };     int n, k, coin[101];     int i, j;       cin >> n >> k;       for (i = 1; i <= k; ++i) {         DP[i] = 10001;                //최대(불가능한 값)로 설정     }       for (i = 1; i <= n; ++i) {         cin >> coin[i];           for (j = coin[i]; j <= k; j++) {             DP[j] = MIN(DP[j], DP[j - coin[i]] + 1);        //min[j] (원래 만들 수 있는 동전의 개수)와                                                          }                                                    //min[j - coin[i] + 1] (j - coin[i]에서 coin[i]를 더해 만드는 동전의 개수)     }       if (DP[k] == 10001) cout << -1 << endl;     else cout << DP[k] << endl;       return 0; } Colored by Color Scripter

cs