[BOJ/C++] 백준 28082 - 기계오리 연구

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

28082번: 기계오리 연구

 

KnapSack을 응용한 DP 문제이다. 

사용할 수 있는 배터리의 총 개수는 N, 기계오리에 장착할 수 있는 배터리의 최대 개수는 K이다. 배터리의 개수가 1 이상, K 이하일 때 만들 수 있는 모든 전력량을 출력하자. 

배터리의 사용 개수가 K 이하인 전력량의 합이 하나라도 있다면 그 전력량은 출력한다. 따라서, 각 전력량의 합을 만들 수 있는 배터리의 최소 개수를 저장한 뒤, 최소 개수가 K개 이하인 배터리의 전력량의 합을 구하면 된다.

 

cache[i] : 배터리를 조합해 만든 전력량이 i일때, 사용한 배터리의 최소 갯수

 

점화식

   cache[0] = 0; 

   cache[i + batttery[j]] = min(cache[i + battery[j]], cache[i] + 1)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 50001
#define INF 987654321
using namespace std; 

int n, k;
vector<int> cache(MAX, INF);

int main() {
	ios_base::sync_with_stdio(false); 
	cout.tie(NULL); cin.tie(NULL); 

	cin >> n >> k;
	cache[0] = 0;
	vector<int> battery(n); 
	for (int i = 0; i < n; i++) cin >> battery[i]; 

	for (int i = 0; i < n; i++) {
		for (int j = MAX - battery[i] - 1; j >= 0; j--) {
			cache[j + battery[i]] = min(cache[j + battery[i]], cache[j] + 1); 
		}
	}
	
	vector<int> ret; 
	for (int i = 1;  i < MAX; i++) {
		if (cache[i] <= k)
			ret.push_back(i); 
	}

	cout << ret.size() << endl;
	for (int i = 0; i < ret.size(); i++)
		cout << ret[i] << " "; 
	cout << endl;
	return 0; 
}