<Baekjoon> #11047 #2293 #2294 Greedy vs Dynamic Programming_동전0, 동전1, 동전2

Google 아니고 Joogle·2022년 3월 18일

algorithm baekjoon dynamicprogramming greedy

Baekjoon

목록 보기

37/47

`💡Idea`

K원을 만드는데 필요한 동전 개수의 최솟값을 만들기 위해서는 동전의 가치가 큰 동전부터 사용해야 한다
동전의 가치가 큰 동전부터 사용하다가 K원에서 현재 동전을 뺐을 때, 0보다 작아진다면 다음으로 가치가 큰 동전을 사용한다

`Source Code`

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> coin;

int solution() {
	int answer = 0;
	for (int i = N - 1; i >= 0; i--) {
		while (K - coin[i] >= 0) {
			K -= coin[i];
			answer++;
		}
	}
	return answer;
}
void input() {
	cin >> N >> K;
	coin = vector<int>(N);
	for (int i = 0; i < N; i++)
		cin >> coin[i];
}
int main() {
	input();
	cout << solution() << endl;
	return 0;
}

동전1 풀이
#2293 동전1 문제는 이미 다룬 적 있으나 한 번 더 짚고 넘어간다

`💡Idea`

K원을 만들기 위해 n가지 종류의 동전을 사용한다
dp[a]=b일 때, a원을 만드는 방법은 b개이다 라고 정한다
현재 동전이 X원이고, Y원을 만들고 싶을 때, 우선 X원은 Y원보다 클 수 없고, Y원에서 X원을 뺀 경우들을 더해주면 된다
즉, dp[Y]=dp[Y]+dp[Y-X]

`Source Code`

#include <iostream>
#include <vector>

using namespace std;

int N, K;

int main() {
	cin >> N >> K;
	vector<int> coin(N);
	vector<int> dp(K + 1);

	dp[0] = 1;

	for (int i = 0; i < N; i++)
		cin >> coin[i];
	for (int i = 0; i < N; i++) {
		for (int j = coin[i]; j <= K; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[K] << endl;
	return 0;
}

`💡Idea`

K원을 만들기 위해 n가지 종류의 동전을 사용하지만, 동전의 개수가 최소가 되도록 구성해야 한다
dp[a]=b 라는 말은 a원을 만들기 위해 필요한 동전의 개수는 b개라는 뜻이다
먼저 dp[]의 모든 값을 MAX로 만들어 준다
현재 동전이 coin[i]원 일 때, dp[j]에는 dp[j-coin[j]]+1 과 dp[j]중에 작은 수가 저장된다.

예를 들어 현재 동전 coin[i]=100원이고, j=500원 이라고 가정하자
500원에서 100원을 뺀 400원을 만들 때 필요한 최소 동전 개수 (=dp[500-coin[100]])에서 100원을 더하는 한 가지 경우를 더하는 경우가 dp[j-coin[j]]+1이다.
모든 경우를 다 검사해보았지만 dp[k]==MAX인 경우는 만들 수 있는 동전이 없다는 뜻이므로 -1을 리턴한다

`Source Code`

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 10001;

vector<int> coin;
int dp[MAX];
int N, K;

int main() {
	cin >> N >> K;
	coin = vector<int>(N+1);

	dp[0] = 0;
	for (int i = 1; i < MAX; i++)
		dp[i] = MAX;
	for (int i = 1; i <= N; i++) {
		cin >> coin[i];

		for (int j = coin[i]; j <= K; j++)
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
	}
	if (dp[K] == MAX) cout << -1 << endl;
	else cout << dp[K] << endl;
	return 0;
}