백준 7579: 앱

문제 요약

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

문제 분류

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

문제 풀이

처음에는 m을 이용하여 DP배열을 만들려고 했지만, m의 범위가 너무 넓으니 그렇게 해서는 안된다. 따라서 다른 방법으로 DP배열을 구축해야하는데, 바로 최소 비용을 이용하면 되겠다.

배열의 인덱스를 최소 비용으로 해서, 각 최소 비용별로 확보할 수 있는 최대의 메모리를 넣으면 된다. 1차원 배열로 구축해도 되지만, 나는 2차원 배열로 구축해보았다. dp[i][j]는, 0~j번째 메모리까지 사용하여 i의 비용으로 확보하는 최대 메모리가 된다. 그리고 DP배열을 순차적으로 탐색하며 m보다 큰 값이 있을 경우 해당 DP의 i가 최소 비용으로 답이 된다.

dp[[i][j]는 우선 dp[i][j - 1]을 포함한다. 즉, dp[i][j]는 dp[i][j]보다 dp[i][j - 1]이 더 크다면 dp[i][j - 1] 이 들어가야 한다. 또한, 비용을 c배열, 확보되는 메모리를 a배열로 가정할 경우, dp[i][j]에서, dp[i - c[j]][j] + a[j]도 비교하여 최대값을 넣어주어야 한다. 결국 j번째 앱을 해제하여, c[j]의 비용으로 a[j]의 메모리를 확보할 경우, dp[i-c[j]][j-1]의 비용에 a[j]의 비용을 합한 것과 그렇지 않은 것(dp[i][j])를 비교하여 최댓값을 넣어야 하기 때문이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
int dp[10001][100];
vector<int> a, c;

int main()
{
	int in, s = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		a.push_back(in);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		s += in;
		c.push_back(in);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= s; j++) {
			dp[j][i] = max(dp[j][i], dp[j][i - 1]);
			if(c[i] <= j)
				dp[j][i] = max(dp[j][i], dp[j - c[i]][i - 1] + a[i]);
		}
	}
	for (int i = 0; i <= s; i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] >= m) {
				printf("%d", i);
				return 0;
			}
		}
	}
}