[백준] 2294번 동전 2

2294번: 동전 2

1~K원을 만들 수 있는 동전의 개수의 최솟값을 배열에 갱신시키며 답을 구해야 하는 DP문제이다.

동전의 가치를 오름차순으로 정렬시킨 후

작은 동전부터 표를 채워나간다.

 

먼저 1~K원을 만드는데 필요한 1원짜리 동전의 개수를 배열에 넣는다.

DP	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
12

 

그 다음 1~K원을 만드는데 필요한 5원짜리 동전의 개수를 배열에 넣는다.

이때 1~4원은 5원짜리로 만들 수 없으므로 앞서 넣어놨던 1원짜리 배열에서 값을 가져오고

5원부터는 1원짜리 배열의 값과 5원으로 만들 수 있는 동전의 개수와 비교하여 더 작은 값을 저장한다.

 

즉, 최솟값(1원짜리로 k원을 만들 때 필요한 개수, k-5원을 만들 때 필요한 어떤 동전의 최소 개수 + 5원짜리 1개)

= 최솟값(DP[k], DP[k-현재 동전] + 1)

라는 식으로 나타낼 수 있다.

 

예를 들어 5원짜리로 7원을 만들고 싶다 가정할 때

최솟값(7, 2 + 1) -> 3

이 되는 것이다.

DP	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

 

12원짜리일 때도 이런 식으로 표를 채우고 나면

DP[2][15]인 3이 답이 된다.

DP	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

 

이론은 이차원 배열로 나타내었지만 실제 구현할 때는 일차원 배열 하나만 있어도 된다.

위에서 파란색으로 표시해둔 값들은

이전 행에서 이미 구해놓은 값들을 그대로 가져온 것이기 때문에

이차원 배열로 구현하면 그 값들을 다 저장시켜야 하는 불필요한 실행이 필요하다.

그래서 일차원 배열로 구현하면 이 과정은 건너뛰고 필요한 순간부터 계산할 수 있다.

 

그리고 또 주의해야할 점은 첫 동전으로 배열을 채워야 할 때

배열의 값이 0으로 초기화 되어 있는 상태라면

최솟값(DP[k], DP[k-현재 동전] + 1)

이 것을 적용하면 항상 답이 0이 나올 수밖에 없다.

그래서 처음에 배열을 가장 높은 동전의 가치보다 큰 수인 100001로 초기화시켜준다.

 

그래서 출력 시 dp[K]의 값이 100001이라면 가지고 있는 동전들로 K원을 만들 수 없다는 의미이므로 -1을 출력해주고

그게 아니라면 dp[K]를 출력해준다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, K, idx = 0;
	cin >> N >> K;
	int coin[101], dp[100001];
	bool chk[100001] = { false };
	for (int n = 0; n < N; n++) {
		cin >> coin[idx];
		if (!chk[coin[idx]] && coin[idx] <= K) {
			chk[coin[idx]] = true;
			idx++;
		}
	}
	sort(coin, coin + idx);
	fill(&dp[0], &dp[K + 1], 100001);
	for (int i = 0; i < idx; i++) {
		dp[0] = 0;
		for (int j = coin[i]; j <= K; j++) {
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
		}
	}
	if (dp[K] == 100001) cout << -1;
	else cout << dp[K];
	return 0;
}