BaekJoon 2294번: 동전 2(C++)

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

2294번: 동전 2

풀이법

1) DP를 활용하여 문제를 풀어보았다. arr라는 DP의 값이 들어갈 배열을 만들었으며, 사용 가능한 동전을 cases라는 vector에 담았다.

2) 각 동전 별로 나올 수 있는 최소의 수를 만들기 위해 algorithm 헤더의 min을 활용하였고, 초기 값으로 dp의 모든 배열을 큰 수(INF)로 설정하였다.

for (int i = 0; i < cases.size(); i++)
{
	for (int j = 1; j <= k; j++)
	{
		if (j - cases[i] < 0)
			continue;
		arr[j] = min(arr[j], arr[j - cases[i]] + 1);
	}
}

만들어진 점화식은 위와 같다.

case[i]: 들어 있는 동전의 값.

예제에 나와 있는 것을 바탕으로 짧게 설명하고자 한다.

 3 15

 1

 5

 12

DP[15]의 경우 min(DP[15-12]+1,DP[15-5]+1, DP[15-1]+1) 의 값을 이용하면 쉽게 구할 수 있다.

cases[i]에 있는 값들을 for문으로 돌려주며 각 DP[j] 값의 최소를 찾아 최종 값인 DP[k]를 구할 수 있었다.

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;

int n, k;
int arr[10001];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> k;
	vector<int> cases;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		cases.push_back(a);
	}
	for (int i = 1; i <=k; i++)
		arr[i] = INF;



	arr[0] = 0;
	for (int i = 0; i < cases.size(); i++)
	{
		for (int j = 1; j <= k; j++)
		{
			if (j - cases[i] < 0)
				continue;
			arr[j] = min(arr[j], arr[j - cases[i]] + 1);
		}
	}
	if (arr[k] == INF)
		cout << -1;
	else
		cout << arr[k];
}