백준 7579번: 앱 - 냅색(배낭) 알고리즘

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

7579번: 앱

1.문제 설명, 접근 방법[알고리즘]

 

다이나믹프로그래밍 문제이자 배낭 문제이다.

"현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여

M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다."

 

M바이트의 메모리를 확보하는 게 아니라

M바이트 이상의 메모리를 추가로 확보해야 한다.

 

나는 처음에 이전에 배낭문제를 풀었던 걸 기억해서

무지성으로 메모리를 기준점을 잡고 비용의 최솟값을 갱신해나가려 했는데

그러면 메모리의 범위가 1 ≤ M ≤ 10,000,000 이어서 배열의 최대 사이즈를 넘어 사용할 수가 없다.

 

그런데 알고보니 메모리를 기준점으로 하는 게 아니라

비용을 기준점으로 하면 비용의 최댓값이 100이고 n의 최댓값이 100이어서

배열을 dy[10001]로 잡아주면 충분하다.

 

 

 

dy[i] 는 cost가 i 일 때 최대 확보한 메모리이다.

 

점화식

dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);

 

문제처럼 입력이 다음과 같을 때

5 60
30 10 20 35 40
3 0 3 5 4

 

 

 

dy 테이블은

mem|cost	0	1	2	3	4	5	6	...	10000
30  |  3	0	0	0	30	30	30	30	30	30
10  |  0	10	10	10	10	40	40	40	40	40
20  |  3	10	10	10	40	40	40	60	60	75
35  |  5	10	10	10	40	40	45	60	60	75
40  |  4	10	10	10	40	50	50	60	80	100

각 문제를 적용했을 때 확보된 메모리가 60이상인 최소의 비용은

 

6이다.

 

 

 

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, mem[101], cost[101], dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

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


	for (int i = 0; i < n; i++) {
		for (int j = 10000; j >= cost[i]; j--) {
			dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
		}
	}

	for (int i = 0; i <= 10000; i++) {
		if (dy[i] >= m) {
			cout << i;
			break;
		}
	}


}