(c++)백준 2294번: 동전 2

www.acmicpc.net/problem/2294

2294번: 동전 2

[풀이]

DP로 풀 수 있는 문제였다.

DP[x]: 가치의 합 x를 얻기 위해 사용한 동전의 최소 개수

점화식

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

 

※처음에 memset으로 DP의 모든 원소를 9999999로 초기화 하려고 했지만 틀렸습니다가 나왔다.

0이나 -1로 초기화 하는 게 아니면 fill을 쓰는걸로..

 

#include <iostream>
//#include <cstring>//memset
#include <algorithm>//min, fill
using namespace std;

int n, k;
int DP[10001];
int coin[101];

void solution() {
	DP[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (coin[i] <= j) {
				DP[j] = min(DP[j], DP[j - coin[i]] + 1);
			}
		}
	}
	if (DP[k] == 9999999)
		cout << -1 << '\n';
	else
		cout << DP[k] << '\n';
}

int main() {
	cin >> n >> k;
	//memset(DP, 9999999, sizeof(DP));
	//memset은 0이나 -1로 초기화할때만 쓰기
	fill(DP, DP + 10001, 9999999);
	for (int i = 1; i <= n; i++) {
		cin >> coin[i];;
	}
	solution();
	return 0;
}