BOJ - 2294번 동전 2 문제풀이 (DP, SET 사용)

문제 소개

n가지  종류의 동전을 갖고, k원의 금액을 최소 개수의 동전으로 만드는 어떻게 보면, 기본적인 dynamic programming 문제입니다.

 

하지만, 풀이하면서 몇 가지 실수가 있었어서 풀이 과정을 간단하게 정리해보려고 합니다.

 

2294번: 동전 2

---

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

3 15
1
5
12

예제 출력

3

---

풀이 과정 정리

우선 앞서 문제 소개에서도 말했다시피 큰 기조로 dynamic programming을 이용한 풀이 방식을 선택했습니다. 왜냐하면, 문제를 해결하기 위해서는 목표 금액을 구성하는 최소 개수의 동전 정보를 구해야 하는데,

 

이를 위해서는 목표 금액보다 작은 금액들을 구성하기 위한 최소 동전 개수 정보를 이용해야 하기 때문입니다.

 

그 중에서도 bottom-up 방식을 적용해 낮은 금액에서부터 목표 금액에 도달하기까지의 과정으로 올라가는 방식으로 구현했습니다.

 

이 과정에서 메모리 초과와 out-of-bound 오류가 계속해서 떳는데

갑자기 런타임 에러랑 메모리 초과가 발생;;

제가 목표 금액을 넘어서는 경우 예외 처리를 했기 때문이라고 생각이 들어 여기저기 바꿔봤지만, 이게 문제가 아니라 조금 더 효율적으로 하기 위해서 set으로 동전 종류를 거르는 과정에서 목표 금액의 최대 한도인 10001 길이의 배열에 coin 가치를 그대로 넣었기 때문이었습니다.

이 부분이 문제가 되어 if 조건절을 추가해 수정했습니다.

이게 왜 문제가 되냐면, 이상하게도 동전의 가치의 한계가 최종 금액의 한도를 넘어서는 100001까지 가능하기 때문이죠

노림수인지는 잘 모르겄다.

그래서 이렇게 문제를 해결했습니다.

 

자세한 설명은 코드로 대체하겠습니다!

---

제출한 코드 (C++)

#include <iostream>
#include <set>
#include <queue>

#define MAX 10001

using namespace std;

// n: 동전의 가지 수, k: 목표 금액
int n, k;

// index: 동전으로 만들 수 있는 금액, value: 금액을 만들기 위한 최소 동전 수
int d[MAX];

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

	cin >> n >> k;

	// set으로 중복 동전을 걸러낸다.
	set<int> coinSet;

	queue<int> q;

	for (int i = 0; i < n; i++) {
		int coinValue;
		cin >> coinValue;

		coinSet.insert(coinValue);
		// 동전 하나로 만들 수 있는 금액부터 표기한다.
		if (coinValue < MAX) {
			d[coinValue] = 1;
			q.push(coinValue);
		}
	}


	while (!q.empty()) {
		int currentValue = q.front();
		q.pop();
		
		// 현재 금액 자체가 목표치를 넘으면 건너띈다.
		if (currentValue > k)
			continue;

		for (auto it = coinSet.begin(); it != coinSet.end(); it++) {
			int coinValue = *it;

			if (currentValue + coinValue > k)
				continue;

			if (d[currentValue + coinValue] == 0) {
				d[currentValue + coinValue] = d[currentValue] + 1;
				// 최솟값을 갱신하는 경우는 queue에 push한다.
				q.push(currentValue + coinValue);
			}
			else if (d[currentValue + coinValue] <= d[currentValue] + 1) {
				continue;
			}
			else {
				d[currentValue + coinValue] = d[currentValue] + 1;
				// 최솟값을 갱신하는 경우는 queue에 push한다.
				q.push(currentValue + coinValue);
			}
		}
	}

	if (d[k])
		cout << d[k];
	else
		cout << -1;

	return 0;
}