[PS] 백준 2293번: 동전 1, 2294번: 동전 2

동전 1 동전 2

dp연습하며 고른 문제이다.

무엇을 기준으로 dp를 할까 엄청 고민하다 결국 힌트를 봐버렸다.

총 가격으로 dp를 한다는 아이디어를 얻자마자 쉽게 풀 수 있었다.

 

dp는 언제쯤 익숙해질까...

이런식으로 n원을 내기 위한 총 경우의 수를 계산하면 된다.

 

동전2는 저기서 경우의수가 대신 n원당 내야하는 동전의 수로 업데이트 하도록 바꿔 쉽게 연계해서 풀었다.

 

// 동전 1
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < static_cast<int>(N); i++)
#define FORL(e, S) for (auto& e : S)

int n, k;
vector<int> coins;
int dp[10001];

int main() {
	cin.tie(NULL)->sync_with_stdio(false);
	cin >> n >> k;
	FOR(i, n) {
		int num; cin >> num;
		coins.push_back(num);
	}
	sort(coins.begin(), coins.end(), less<int>());
	
	dp[0] = 1;
	FORL(coin, coins) {
		for (int i = 0; i <= (k - coin); i++) {
			if (dp[i]) dp[i + coin] += dp[i];
		}
	}
	cout << dp[k] << endl;
	return 0;
}

// 동전 2
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < static_cast<int>(N); i++)
#define FORL(e, S) for (auto& e : S)

int n, k;
vector<int> coins;
int dp[10001];

int main() {
	cin.tie(NULL)->sync_with_stdio(false);
	cin >> n >> k;
	FOR(i, n) {
		int num; cin >> num;
		coins.push_back(num);
	}
	sort(coins.begin(), coins.end(), less<int>());
	
	FORL(coin, coins) {
		for (int i = 0; i <= (k - coin); i++) {
			if (i && !dp[i]) continue;
			if (!dp[i + coin]) dp[i + coin] = dp[i] + 1;
			else dp[i + coin] = min(dp[i + coin], dp[i] + 1);
		}
	}
	cout << ((dp[k]) ? dp[k] : -1) << endl;
	return 0;
}