[알고리즘] C++ 백준 2294 동전2

백준 2294

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

2294번: 동전 2

풀이 전 나의 생각

동전, 동전1에 이어서 나온 동전2 문제다.

문제 모두 동전을 이용하여 목표 가치를 만드는데에 중점을 두고 있다.

 

이번 문제 동전2에서는 동전1과 달리 모든 경우의 수를 구하는 것이 아닌 최소가 되는 경우를 구해야 한다.

즉, DP 점화식의 재활용이 불가능하기 때문에 새로운 점화식을 구해내야 한다.

 

그럼 이제 모든 경우의 수가 아닌 최소의 경우를 구해야하기 때문에

DP가 무엇을 의미해야 하는지 생각해 봐야한다.

DP에는 뭔가 어떤 가치 K가 있다면 이를 만들기 위해 사용해야 할 동전의 개수가 들어가야 할 것 같다.

 

그럼 예를 들어서 현재 만들어야 할 목표가치가 5원이고 현재 사용해야 할 동전이 3원이라고 가정해보자.

우선 무조건 3원을 사용한다는 가정이기 때문에 탐색을 할때마다 자신의 동전을 추가해줘야 한다.

그럼 3원을 추가했으니 목표가치 5원에서 3원을 뺀 2원을 만들 수 있는 최소 동전 개수를 추가적으로 더해주면 된다.

 

이를 점화식으로 표현하면

1 + dp[j - coin[i]] 로 표현할 수 있다. 여기서 i는 현재 탐색하고 있는 동전의 순번이고

j는 현재 탐색하고 있는 가치를 의미한다.

 

문제에서 요구하는 것은 최소의 개수를 구해야 하기 때문에 dp[0]을 제외한 모든 dp값은

최대 목표가치 값 + 1 로 설정해주고 앞서 말한 점화식을 

dp[j] = min(dp[j], 1 + dp[j - coin[i]]) 로 변경하면 문제의 답을 쉽게 구해낼 수 있다.

 

조금 더 추가 설명을 하자면

목표가치를 1원부터 10원까지 탐색하며  동전1원으로 만들 수 있는 최소 개수를 구한다고 하면

(조건 dp[0] = 0 -> 이유는 동전의 첫 탐색은 dp[0]이 나오며 이를 0으로 설정해야 본인의 동전 개수를 추가한 1을

만들 수 있다.)

dp[1] = 1 + dp[0] (1개) ->  목표가치 1원을 동전 1원으로 만들 수 있는 경우는 현재 동전 1원 하나 사용

 

dp[2] = 1 + dp[1] (2개) -> 목표가치 2원을 동전 1원으로 만들 수 있는 경우는 현재 동전 1원 하나 사용 + 1원을 만들 수 있는 최소 동전 개수

 

dp[3] = 1 + dp[2] (3개) -> 목표가치 3원을 동전 1원으로 만들 수 있는 경우는 현재 동전 1원 하나 사용 + 2원을 만들 수 있는 최소 동전 개수....

 

이런 식으로 현재 자신의 동전을 추가하면서 목표 가치를 만들 수 있는 동전의 개수를 갱신하며 최소값을

구해나가면 된다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int coin[101];
int dp[10001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> coin[i];
	}

	fill(begin(dp),end(dp), 10001);
	dp[0] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = coin[i]; j <= k; j++)
		{
			dp[j] = min(dp[j], 1 + dp[j - coin[i]]);		
		}
	}

	if (dp[k] == 10001) cout << -1;
	else cout << dp[k];
}