백준 7579 앱

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

7579번: 앱

 

DP와 Knapsack이 결합된 문제이다.

 

이 문제가 Knapsack 문제라는 걸 파악하기만 한다면, 푸는 거 자체는 그리 어렵지 않다고 생각한다.

 

보통 최대 Cost를 Column으로 하고 각각의 배낭(여기서는 앱)을 Row로 하기때문에 이 문제의 최대 M이 1,000,000 이므로 KnapSack 문제가 아니라고 생각했었다.

 

KnapSack의 시간복잡도는 O(N * M) 즉 100 * 1,000,000 = 10억 이 된다고 생각했기 때문이다.

 

하지만 이 문제의 Cost 최대는 100 * 100 = 1,000,000 밖에 안된다는 걸 확인하면 Knapsack을 시도할 만하다고 생각할 것이다.

 

이 해답의 for문이 특이하다 Knapsack 문제를 풀때는 Cost를 기준으로 for문을 진행하는데

 

이 문제는 배낭(이 문제에서는 앱)을 기준으로 for문을 진행한다.

 

요즘들어 자력으로 푸는 문제가 줄어들고 있다. 반성하게 된다... 

/* 앱 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long int 

using namespace std;

vector<int> memory, cost, res;
int n, m;

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

	cin >> n >> m;
	memory.resize(n);  cost.resize(n);

	int cost_sum = 0;
	for (int i = 0; i < n; i++) cin >> memory[i];
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
		cost_sum += cost[i];
	}
	
	res.resize(cost_sum + 1, 0);
		
	
	for (int i = 0; i < n; i++) {
		for (int j = cost_sum; j >= cost[i]; j--) {
			res[j] = max(res[j], res[j - cost[i]] + memory[i]);
		}
	}

	int i;
	for (i = 0; res[i] < m; i++);
	cout << i << '\n';
	return 0;
}