백준 / BOJ / 7579 앱 C++

www.acmicpc.net/problem/7579

7579번: 앱

처음에 문제를 잘못 읽어서 아래 코드에서 apps가 메모리, Mem이라는 녀석이 비용에 해당합니다. (c1,c2,....)

 

이 문제의 핵심은 가능한 메모리 별로 dp를 구하는 것입니다. 처음에 문제 접근을 잘못해서 구현이 되지 않아 구글링으로 힌트를 조금 얻었습니다.

 

dp[i]를 비용이 i일 때 가능한 메모리의 최댓값으로 처리합니다. 여기서 최댓값으로 처리하는 이유는, 최종적으로 계산할 때, 앞에서 부터 dp를 앞에서부터 탐색하면서 메모리 (dp[i]의 값) 가 M 이상이기만 하면 되므로, 처음으로 M이상이 되는 i값이 문제에서 요구하는 비용의  최솟값이기 때문입니다.

 

c1,c2,... 의 최대값이 100이고, N의 최댓값이 100이므로 가능한 비용의 최댓값은 10000이므로 dp[10001]을 이용합니다.

그리고 가장 중요한 점화식은 아래와 같습니다.

 

for i = 0 to i < N :

    for j = 10000 to j >= Mem[i] :

        dp[ j ] =max(dp[ j ], ( dp[ j - Mem[ i ] ] + apps[ i ] ))

  

dp[ j ] : 비용이 j 일 때 가능한 최대 메모리

dp[ j - Mem[ i ]] : i번째 비용을 제외한 최대 메모리

apps[ i ] : i번째 메모리

이므로 위 경우를 다이나믹 프로그래밍으로 계산하면 됨을 알 수 있습니다.

 

코드는 아래와 같습니다.

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

using namespace std;

int N, M;
int* apps;
int* Mem;
int dp[10001];
int res;

void make_input()
{
	cin >> N >> M;
	apps = (int*)malloc(sizeof(int) * N);
	Mem = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
		cin >> apps[i];
	for (int i = 0; i < N; i++)
		cin >> Mem[i];
	memset(dp, 0, sizeof(dp));
}

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

	for(int i=0;i<=10000;i++)
		if (dp[i] >= M)
		{
			res = i;
			break;
		}

	cout << res;
	
}