[백준] 7579번 앱 C++ 문제풀이

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

7579번: 앱

문제 풀이

맨 처음에는 그리디로 그냥 cost가 작을수록, cost가 같다면 메모리가 클수록 앞으로 배치되게 정렬한 후 풀었더니 틀렸다.

원래 0-1 Knapsack 문제는 그리디로 풀면 최적해를 보장하지 않는다.

따라서 dp로 문제를 풀었다.

위의 식 P[i,w] 는 아이템이 i개있고, w까지 한도일 때 최적의 v를 구하는 공식이다.

이 문제에서는 메모리의 경우 10,000,000 이므로 w로 사용하기 적합하지 않다.

따라서 i는 아이템의 수 n ,  w는 비용인 c , v는 m을 의미하게 했다.

따라서 이 문제에서 P[i,w] 의 의미는 아이템이 i개 있고, cost가 w 일 때 최대의 m을 구하는 문제로 바뀐다.

코드는 아래와 같다.

소스 코드

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

int n, m;
vector<pair<int,pair<int, int>>> app;
int dp[101][10001] = { 0 };

int main() {
	cin >> n >> m;
	int mem[101] = { 0 };
	for (int i = 0; i < n; i++) {
		cin >> mem[i];
	}
	int sum = 0;
	int cost[101] = { 0 };
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
		sum += cost[i];
	}

	for (int i = 0; i < n; i++) {
		int c = cost[i];
		int memory = mem[i];
		if (c != 0) {
			app.push_back(make_pair(memory / c, make_pair(c, memory)));
		}
		else {
			app.push_back(make_pair(0, make_pair(c, memory)));
		}
	}

	sort(app.begin(), app.end()); // 정렬

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= sum; j++) {
			if (app[i - 1].second.first <= j) {
				dp[i][j] = max(app[i - 1].second.second + dp[i - 1][j - app[i - 1].second.first], dp[i - 1][j]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	for (int j = 0; j <= sum; j++) {
		if (dp[n][j] >= m) {
			cout << j << '\n';
			break;
		}
	}
}