BOJ 7579 - 앱

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

 

접근

앱 중 최소비용으로 최대의 메모리를 확보하는 문제이다.

휴대폰 메모리 M이 정해져있기 때문에, 냅색 문제로 해결할 수 있다.

냅색 문제에서 weight와 value는 각각 앱의 비용과 앱의 메모리를 의미한다.

 

기존 냅색 문제에서 DP[i][j]의 의미는 i번째 앱 시점에서 j의 코스트로 가지는 최대 메모리 사용량이다.

이중for문을 돌면서 DP[i][j]를 구하면된다. 

그리고 마지막에 DP[i][j]가 M이상인 것 중 첫번째가 답이 된다.

왜냐하면 i번째를 살펴볼때 j가 0부터 total(사용할 수 있는 최대 코스트)까지를 살피는 경우는 i번째 앱이 포함될 수도 있고 아닐 수도 있기 때문이다.

 

 코드

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

using namespace std;

#define MAX 9999999

int dp[101][10001]; // i번째 앱까지 확인할때, j코스트로 확보할 수 있는 최대 메모리
int n, m;
int value[101]; // 바이트
int weight[101]; // 비용
int total;

int main() {
	/*ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);*/
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> value[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> weight[i];
		total += weight[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= total; j++) {
			if (j - weight[i] >= 0) {
				int no = dp[i - 1][j];
				int yes = dp[i - 1][j - weight[i]] + value[i];
				if (no > yes) {
					dp[i][j] = no;
				}
				else {
					dp[i][j] = yes;
				}
			}
			else {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			}
		}
	}
	for (int i = 0; i <= total; i++) {
		if (dp[n][i] >= m) { 
			cout << i;
			break;
		}
	}
}

 

참고

https://www.youtube.com/watch?v=uggO0uzGboY

https://cocoon1787.tistory.com/319

[C/C++] 백준 7579번 - 앱 (DP)