[백준] 7579번: 앱 (c++)

 

문제

---

현재 N개의 앱, \(A_1\), ..., \(A_N\)이 활성화 되어 있다고 가정하자. 이들 앱 \(A_i\)는 각각 \(m_i\) 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 \(A_i\)를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 \(c_i\) 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 \(A_1\), ..., \(A_N\) 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 \(c_i\)의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

 

7579번: 앱

 

문제조건

---

• 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000
• 1 ≤ \(m_1\), ..., \(m_N\) ≤ 10,000,000
• 0 ≤ \(c_1\), ..., \(c_N\) ≤ 100
• M ≤ \(m_1\) + \(m_2\) + ... + \(m_N\)

 

풀이

---

dp를 사용해서 푸는 문제이다. 문제에서는 M바이트를 확보하는 최소비용을 구하라고 나와있지만 거꾸로 생각해서 비용당 최대 메모리 크기를 구하면 된다. 점화식을 구해보면 다음과 같다

dp[j] = max(dp[j], dp[j-cost[i]] + memory[i])

j비용으로 구할 수 있는 최대 메모리 크기는 i번째 메모리를 포함한 값과, 포함하지 않은 값 중 최대값이다. 문제에서 주어진 예시를 위 점화식에 맞춰서 구해보자

비용(j)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0번	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
1번	10	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
2번	10	10	10	40	40	40	60	60	60	60	60	60	60	60	60	60
3번	10	10	10	40	40	45	60	60	75	75	75	95	95	95	95	95
4번	10	10	10	40	50	50	60	80	80	85	100	100	115	115	115	135

주어진대로 값을 다 구해보면 가장 마지막 줄(4번)줄의 결과가 나오게 된다. 이렇게 구한 dp값을 돌며 M보다 크거나 같은 값이 나오면 그 인덱스가 구하고자 하는 최소비용이다.

 

코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int memory[101];
int cost[101];
int dp[10001];

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> memory[i];
	}

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

	for (int i = 0; i < N; i++) {
		for (int j = costSum; j >= cost[i]; j--) {
			dp[j] = max(dp[j], dp[j - cost[i]] + memory[i]);
		}
	}

	for (int i = 0; i <= costSum; i++) {
		if (dp[i] >= M) {
			cout << i;
			return 0;
		}
	}
}