[BOJ/백준 2294][C++] 동전 2

문제

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

백준 2294

 

문제 내용

동전 n개를 입력하여 k원을 만들려고 한다.

최소한의 동전 개수를 사용하여 k원을 만들려고 할 때, 동전 개수를 출력하면 된다.

 

문제 풀이

이 문제는 아래의 [백준 11047 동전 0]과 유사하다.

[BOJ/백준 11047][C++] 동전 0

동전 0 문제에서는 주어지는 동전의 가치가 서로 배수관계에 있기 때문에 greedy 하게 풀 수 있었다.

하지만, 이 문제에서 동전의 가치는 서로 배수관계가 아니기 때문에, greedy로 풀지 못한다.

 

나는 이 문제를 dp로 풀었다.

먼저, 동전을 money배열에 입력받는다.

또한 k의 범위가 10,000 이하이기 때문에, dp배열을 10001로 초기화시켜둔다.

 

이후, 반복문을 돌면 된다.

money배열의 동전을 사용해야 하기 때문에, 반복문으로 1~n의 범위를 돈다.

그 안에서, money[i]값을 가지고 dp배열 전체를 update 시켜야 한다.

money[i]의 값으로 dp[j]의 값을 더 작게 만들 수 있으면 update 한다.

따라서 dp[j]의 값과, dp[j-money[i]]+1의 값을 비교하면 된다.

 

코드

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

int dp[10001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n,k;
	cin >> n>>k; //n개의 동전, k원을 만들어야 한다.
	vector<int>money(n+1);
	for (int i = 1; i <= n; i++) cin >> money[i];

	//문제 해결
	for (int i = 1; i <= k; i++) dp[i] = 10001; //최솟값을 구하기 위함

	for (int i = 1; i <= n; i++) { // money[i] 동전을 가지고
		for (int j = money[i]; j <= k; j++) { // 최솟값을 만들 수 있으면 갱신
			dp[j] = min(dp[j], dp[j - money[i]] + 1);
		}
	}

	//결과 출력
	if (dp[k] == 10001) cout << -1 << '\n';
	else cout << dp[k] << '\n';
}