백준 - 동전 2 (2294) [C++]

 이 문제는 dp를 이용해서 푸는 문제이다. dp 배열을 해당 금액을 만들 수 있는 최소의 코인 개수로 설정하면 쉽게 풀 수 있는 문제이다. 시간 제한이 1초이므로, 1억번의 연산만으로 끝내야 한다. for 문마다 최대 100번의 루프가 돌아야 하므로, 탐색할 수 있는 금액의 최대 한도는 1,000,000원이다. 따라서 MAX를 백만으로 설정해서 문제를 풀었다.

 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

#define MAX 1000000

int dp[MAX + 1];

void init() {
	for (int i = 0; i < MAX + 1; i++) {
		dp[i] = MAX;
	}
}

int main() {
	int n, k;
	vector<int> coin;
	cin >> n >> k;

	init();

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		coin.push_back(temp);
		dp[temp] = 1;
	}

	for (int i = 1; i < MAX + 1; i++) {
		for (int c : coin) {
			int prev = i - c;
			if (prev <= 0) {
				continue;
			}
			dp[i] = min(dp[prev] + 1, dp[i]);
		}
	}

	if (dp[k] == MAX) {
		cout << -1 << '\n';

		return 0;
	}
	cout << dp[k] << '\n';

	return 0;
}