백준 7579(앱) c++

문제

7579번: 앱

현재 사용하고 있는 n개의 메모리 공간과 메모리 제거 비용이 주어지고, 최소 필요한 메모리 공간인 m이 주어지면  

n개의 메모리에서 m만큼 제거하면서 최소 비용이 나오게끔 하는 문제입니다.

예를 들어 n = 5이고 n개의 메모리 공간은 {30, 10, 20, 35, 40} 이고, 각각의 메모리 제거 비용은 {3, 0, 3, 5, 4} 라고 하고

m = 60이라 하면, n개의 메모리 중 {30, 10, 20}을 제거하면 제거 비용은 {3, 0, 3} 이므로 총 6이 되어서 

60의 크기를 제거하기 위한 최소비용이 됩니다.

 

즉, 총 60이상의 메모리를 제거하면서 최소비용이 되게끔하는 것입니다.

이를 다시 풀어쓰면 각 비용당 제거할 수 있는 최대 메모리 크기를 생각하면 문제를 해결할 수 있을 것입니다.

 

이는 가방의 크기(비용)당 넣을 수 있는 최대 무게(메모리의 크기)를 구하는 것과 같습니다.

결국 Knapsack 알고리즘입니다.

 

int memory[101]; //메모리 크기 저장
int cost[101]; //메모리 당 비용 저장
int sum = 0; // 전체 비용

int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> memory[i];
for (int i = 1; i <= n; i++) {
	cin >> cost[i];
	sum += cost[i];
}

입력 부분입니다.

우리는 현재 입력받은 정보의 최대 비용만큼만 확인하면 되기 떄문에 sum을 이용해 모든 비용의 누적합을 구해줍니다.

 

이제 knapsack알고리즘을 구현할 차례 입니다.

dp[i][j] = i번째 메모리까지 확인하고 j의 비용을 얻을 수 있는 최대의 메모리 입니다.

결국 dp[n][]가 m이상이면 정답입니다.

 

위의 예시를 살펴보면

1번째 메모리 크기 :  30, 비용 3

2번째 메모리 크기 : 10, 비용 0

3번째 메모리 크기 :  20, 비용 3

4번째 메모리 크기 :  35, 비용 5

5번째 메모리 크기 :  40, 비용 4

를 바탕으로 다음과 같은 dp 배열을 만들 수 있습니다.

int dp[101][10001];
for (int i = 1; i <= n; i++) {
	for (int j = 0; j <= sum; j++) {
		if (j - cost[i] >= 0)
			dp[i][j] = max(dp[i-1][j], dp[i - 1][j - cost[i]] + memory[i]);
		dp[i][j] = max(dp[i][j], dp[i - 1][j]);
	}
}

dp배열은 [101][10001]로 설정하였습니다. n의 크기가 최대 100이고, 메모리 한개당 비용의 최대 크기는 100이므로

100 * 100 = 10000이기 때문입니다.

다음은 그냥 knapsack알고리즘과 같습니다.

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

마지막으로 dp[n][i]의 크기가 m 이상일 때의 i는 n번째 메모리까지 확인하고 i의 비용을 얻을 수 있는 최대 메모리입니다.

i를 출력해 줍니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
int memory[101];
int cost[101];
int sum = 0;
int dp[101][10001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> memory[i];
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
		sum += cost[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= sum; j++) {
			if (j - cost[i] >= 0)
				dp[i][j] = max(dp[i-1][j], dp[i - 1][j - cost[i]] + memory[i]);
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}
	for (int i = 0; i <= sum; i++) {
		if (dp[n][i] >= m) {
			cout << i;
			break;
		}
	}

	return 0;
}