[백준] 2293번, 2294번 동전 1 & 2 : C++ 풀이

 

2293번: 동전 1

 

다이나믹 프로그래밍으로 풀이했고

흔한 동전 처리 문제이다.

 

---

 

2293 Solution

#include <iostream>
using namespace std;

int main()
{
	int n, k;
	int coins[101];
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> coins[i];
	}
	long long dp[10001] = { 0 };
	long long result = 0;
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			result = j + coins[i];
			if(result <= k) dp[result] += dp[j];
		}
	}
	cout << dp[k];
}

 

동전 1에서는 주어지는 동전의 가치가 모두 다르고

동전의 구성이 같다면 순서와 관계 없이 같은 걸로 처리한다.

그러므로, 동전을 기준으로 경우의 수를 처리해야 한다.

 

예를 들면,

1, 2, 5원의 동전이 있을 경우에

1원 동전으로 이루어진 경우를 모두 dp에 저장하고

2원 동전을 추가했을 때의 경우를 모두 dp에 저장하고

5원 동전을 추가했을 때 경우를 모두 dp에 저장하는 식으로 구하면

동전의 구성이 다른 경우만 구할 수 있다.

 

여기서 result 값이 k보다 크면

OutofBounds 에러가 발생할 수 있으므로 예외 처리 했다.

 

 

 

2294번: 동전 2

 

동전 2 문제는 동전 1 문제와 비슷하되

다른 조건이 존재한다.

 

동전의 가치가 같은 동전들도 존재하며

최소의 동전들로 가치의 합을 이루어야 한다.

 

여기서 동전 1과 다르게동전을 중심으로 경우를 계산하기 힘들기 때문에

가치의 합(dp)을 기준으로 경우를 계산해주었다.

 

---

2294 Solution

#include <iostream>

#define MAX 1000000

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	int coins[101] = { 0, };
	long long dp[10001];
	for (int i = 0; i <= k; i++)
	{
		dp[i] = MAX;
	}

	for (int i = 1; i <= n; i++)
	{
		cin >> coins[i];
	}
	dp[0] = 0;
	int result = 0;
	for (int i = 0; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			result = i + coins[j];
			if (result <= k)
			{
				dp[result] = min(dp[result], dp[i] + 1);
			}
		}
	}
	if (dp[k] == MAX) cout << -1;
	else cout << dp[k];
}

 

MAX 값이 1만보다 크면 된다.

(문제 조건에서 k가 1만까지 이므로)

 

동전 1과 다르게 for문을 보면

k값을 기준으로 먼저 경우의 수를 계산한다.

(동전 1에서 인덱스 i, j와 동전 2에서 i, j가 서로 반대이므로 주의)

 

여기서 예제를 경우로 들었을 때 result가 5일 때

1원 5개와 5원 1개의 경우가 있다.

1원, 5원의 순서에 관계 없이 min에 의해

더 적은 값으로 할당된다.

 

 

주의해야 할 점은

k값을 이루지 못 할 경우 -1을 출력해야 하므로

dp[k] 가 MAX (변화가 없을 때)인 경우에 예외 처리를 해주도록 해야 한다.