BOJ 2293 동전 1, 2294 동전 2

www.acmicpc.net/problem/2293

2293번: 동전 1

 

시간이 0.5초, 메모리 제한이 무려 4MB 인 DP 문제다. 메모리 제한 때문에 탑-다운보다는 바텀-업 방식으로 해결했다.

d [i]는 i를 만드는데 필요한 경우의 수로 놓고 풀어보면

 

d [j] += d [j- ar [i]] 가 식이 된다.

 

d [j]를 만드는 경우의 수는 d [j- ar [i]] 를 어떻게든 잘 구해놓고 d [j - ar [i]] 를 더해준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int ar[101], n, k, d[10001];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> k;

	for (int i = 0; i < n; i++) cin >> ar[i];
	
	d[0] = 1;
	for (int i = 0; i < n; i++) 
		for (int j = ar[i]; j <= k; j++) 
			d[j] += d[j - ar[i]];

	cout << d[k] << endl;

	return 0;
}

 

www.acmicpc.net/problem/2294

2294번: 동전 2

 

동전 2는 필요한 '최소'의 동전 갯수를 구하는 문제다. 탑-다운으로 해서 메모이제이션 하면 직관적으로 풀 수 있는 문제였다.

 

기저 사례를 보면 n == N 이 되는 경우에 k 가 0 이라면 동전을 잘 사용해서 K 값을 만든 것이니 0을 리턴해주고

아니라면 불가능한 값을 리턴해준다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N, K, ar[101], d[101][10001];
const int INF = 1e9;

int go(int n, int k) {
	if (n == N) return k == 0 ? 0 : INF;
	if (d[n][k] != -1) return d[n][k];

	int ret = 0;
	if (k < ar[n]) ret = go(n + 1, k);
	else ret = min(go(n + 1, k), go(n, k - ar[n]) + 1);
	return d[n][k] = ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> ar[i];
	memset(d, -1, sizeof(d));

	int ans = go(0, K);

	if (ans == INF) cout << -1 << endl;
	else cout << ans << endl;

	return 0;
}