[👊DP뿌시기 #13-2] (BOJ 2293) 동전 2

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

2294번: 동전 2

---

접근법

동전 1 문제와 비슷한 문제이다.

동전 1 문제는 가지 수를 구하는 문제이지만, 동전 2 문제는 사용되는 동전의 최소 개수를 구하는 문제이다.

 

1원으로 2원을 만들때 동전의 최소 개수는?

DP[2-1] + 1개

1원으로 3원을 만들때 동전의 최소 개수는?

DP[3-1] + 1개

 

2원으로 3원을 만들때 동전의 최소 개수는?

DP[3-2] + 1개

2원으로 4원을 만들때 동전의 최소 개수는?

DP[4-2] + 1개

 

coin[j]를 가지고 i원을 만들때 동전의 최소 개수는?

DP[i-coin[j]] + 1

 

동전이 예시처럼 3 종류가 있을때, 각 동전마다 최소 개수가 다를 수 있기 때문에 기존 DP보다 작을때만 값을 업데이트한다.

따라서,

DP[i] = min(DP[i-coin[j]]+1, DP[i])

 

주의할 점이 있다.

위 점화식을 그대로 하게되면 0이 출력된다.

왜냐하면 DP값이 0으로 초기화되어있기 때문이다.

따라서, DP값을 최고 개수보다 1 많은 상태로 초기화해야한다. (init 함수 참고)

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 10001

using namespace std;

int dp[MAX];
vector<int> v;
int n, k;

void init() {
	for (int i = 1; i <= k; i++) {
		dp[i] = 10001;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(),v.end());
	init();
	for (int i = 0; i < n; i++){
		for (int j = v[i]; j <= k; j++) {

			
				dp[j] = min(dp[j - v[i]] + 1, dp[j]);
		}
	}
	if (dp[k] == MAX)cout << -1;
	else
	cout << dp[k];
}

같이보기

https://parvegoongame.tistory.com/75

[👊DP뿌시기 #13] (BOJ 2293) 동전 1