백준 7579 앱

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 여러개의 앱이 실행 중일때 각 앱을 비활성화 하는 비용과 그로인해 얻을 수 있는 메모리가 있을 때 요구하는 메모리를 확보할 수 있는 최소의 비용을 구하는 문제입니다. 모든 경우를 다 해봐야 하므로 dp를 이용하여야 합니다.

 

dp식을 어떻게 만들지 생각해 보면 2차원 dp를 선언하고 dp[i][j] 의 의미는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미합니다. 따라서 아래식과 같이 dp[i][j]에서 i번째 앱을 비활성화 시킨 경우와 그렇지 않은 경우중 max값을 취하면서 반복문을 돌아주어야 합니다.

 

if(j-cost[i] >= 0)
             dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]]+byte[i]);  //i번째 앱 활성화

 

dp[i][j] = max(dp[i][j], dp[i-1][j]); //i번째 앱 비활성화

 

이러한 값들중 요구 하는 바이트를 만족하는 가장작은 코스트 값j를 찾으면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int dp[110][11000];


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int mem[110];
	int cost[110];

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> mem[i];

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

	dp[0][cost[0]] = mem[0];
	int ans = 100000;
	if (mem[0] >= M) ans = cost[0];


	for (int i = 1; i < N; i++) {
		for (int j = 10000; j >= 0; j--) {
			
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);

			if (j - cost[i] < 0) continue;
						
			dp[i][j] = max(dp[i][j], dp[i-1][j - cost[i]] + mem[i]);

			if (dp[i][j] >= M) ans = min(ans, j);			
		}
	}
	cout << ans;


	return 0;
}