[백준] 2294번 동전 2

링크

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

2294번: 동전 2

풀이

 

위의 문제는 사용한 동전의 최소 개수를 찾는 문제인데

다들 가장 큰 동전 부터 가장 작은 동전까지 이용하여 풀면 되겠지? 라는 생각을 하셨겠지만 여러 반례가 있죠?

그래서 가장 작은 값의 동전부터 가장 큰 동전까지 사용한 개수를 DP배열에 카운트하여 최소개수를 찾을수 있습니다.

 

 

1원짜리 동전으로 0~15원까지 만들수 있는 개수를 표로 나타내면 다음과 같습니다.

	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

이때 가지고 있는 동전으로 0원을 만들수 있는 경우의 수는 동전을 하나도 사용하지 않았을때 이므로 0으로 나타 내었습니다.

 

그리고 그 다음 동전인 5원으로 만들수 있는 개수를 표로 나타내기 전에 생각을 해봐야 할 것이 있습니다.

1원과 5원으로 5원, 10원, 15원을 만들수 있는 최소의 갯수는 5원 1개, 5원 2개, 5원 3개 입니다.

 

그렇다면

6원은 5원 1개 + 1원 1개 = 2개

11원은 5원 2개 + 1원 1개 = 3개

....

 

	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3

 

그렇다면 마지막으로 12원을 이용 하였을 때는

	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12원	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

12원을 만들기 위해서는 12원 1개를 이용하면 되고

15원을 만들기 위해서는 12원 1개와 1원 3개 = 4개를 이용하여 만들면 되지만

이미 5원 3개 = 3개 를 이용하면 최소의 개수를 이용하여 만들수 있기 때문에 4가 아닌 3이 들어가도록 합니다.

 

그렇다면 최종적인 DP 배열은 다음과 같습니다.

	0원	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원	11원	12원	13원	14원	15원
1,5, 12	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

 

코드를 봐도 이해가 안되신다면 공책에 표를 그려 하나씩 천천히 생각하시면 될것같습니다 !.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define INF 2e9
#define SIZE 10010

using namespace std;

typedef long long int ll;

vector<int> cost;

int dp[SIZE];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K; cin >> N >> K;

	for (int i = 0; i < N; i++) {
		int c; cin >> c;
		cost.push_back(c);
	}

	sort(cost.begin(), cost.end());
	fill(dp, dp + SIZE, 20000);

	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		int start = cost[i];

		for (int s = start; s <= K; s++) {
			dp[s] = min(dp[s - start] + 1, dp[s]);
		}
	}

	cout << (dp[K] == 20000 ? -1 : dp[K]);
}