[이코테] C++ 효율적인 화폐 구성 - DP

문제

• N가지 종류의 화폐가 있다.
• 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
• 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력 조건

• 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
• 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

입력 예시

2 15
2
3

3 4
3
5
7

출력 예시

5

-1

접근 방법

1. 입력된 화폐 마다 M에 도달할 때까지 그전에 있는 값들에 도달하기 위해 걸리는 횟수를 계산한다.
   즉, 2원이 15원에 도달하기 위해서. 2~15까지. 2원은 1번, 4원은 2번, 6원은 3번... 이런식으로
   
   그리고 다음 화폐인 3원도 15원에 도달하는 데 걸리는 횟수를 계산한다. 그중 6원에 도달하기 위해서 2원은 3번, 3원은 2번이 걸린다. 그러면 우리는 3과 2중 작은 값인 2를 선택해야한다.
2. 2가 되기 위해서는 0에서 2를 더하는 작업
   4가 되기 위해서는 2에서 2를 더하는 작업
   dp[2] = dp[0] + 1
   dp[4] = dp[2] + 1
   6은 어떻게 될까
   dp[6] = d[4] + 1, dp[3] + 1 중 최소값을 구하면 된다.

풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> arr;

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}

	vector<int> d(m + 1, 10001);

	d[0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = arr[i]; j <= m; j++) {
			if (d[j - arr[i]] != 10001) {
				d[j] = min(d[j], d[j - arr[i]] + 1);
			}
		}
	}

	if (d[m] == 10001) cout << -1 << "\n";
	else cout << d[m] << "\n";
}

참고

• 이것이 취업을 위한 코딩 테스트다. with python (by 나동빈)