백준 7579 앱

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

7579번: 앱

 

 

 

EXPLANATION

 

메모리 M 바이트를 확보하기 위한 최소의 비용을 구해야 한다.

0의 비용부터 모든 비용을 합친 비용까지 각 각의 모든 비용에 대해서 얻을 수 있는 각 각의 최대의 메모리를 구한 후,

최대 메모리가 M인 비용을 구하면 된다.

 

dp[i][j]는 i번째 앱까지 확인했을 때, j의 비용으로 얻을 수 있는 최대 메모리.

 

i번째 앱의 비용이 비용 j보다 작으면,

i번째 앱의  메모리와 (i -1)번째까지 앱을 탐색했었을 때, (j - i번째 앱의 비용)으로 얻을 수 있는 최대 메모리를 더한 후,

(i -1)번째까지 앱을 탐색했었을 때, j비용으로 얻을 수 있는 최대 메모리와 비교.

 

i번째 앱의 비용이 비용 j보다 크면,

(i -1)번째까지 앱을 탐색했었을 때, j비용으로 얻을 수 있는 최대 메모리.

 

// dp[i][j] == i번째 앱까지 탐색했을 때 
// j비용을 소모해서 얻을 수 있는 최대 메모리
for (int i = 1; i <= N; i++)
{
    for (int j = 0; j <= sum; j++)
    {
        if (j - cost[i] >= 0)
            dp[i][j] =  max(dp[i-1][j], dp[i - 1][j - cost[i]] + memory[i]);
        else 
            dp[i][j] = dp[i - 1][j];


    }
}

 

시각화해서 보자.

ex)

예제 입력

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

3 + 0 + 3 + 5 + 4 =15

 

 

참조: https://cocoon1787.tistory.com/319

 

CODE

#include<iostream>
using namespace std;

int N, M, ans, sum;
int memory[101], cost[101];
int dp[101][10001]; //(앱의 최대 갯수: 100) * (비용의 최댓값: 100)

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

	for (int i = 1; i <= N; i++) 
        cin >> memory[i];
	for (int i = 1; i <= N; i++) 
	{
		cin >> cost[i];
		sum += cost[i];    //최대 비용을 구하기 위해서.
	}

	// dp[i][j] == i번째 앱까지 탐색했을 때 
	// j비용을 소모해서 얻을 수 있는 최대 메모리
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= sum; j++)
		{
			if (j - cost[i] >= 0)
				dp[i][j] =  max(dp[i-1][j], dp[i - 1][j - cost[i]] + memory[i]);
            else 
                dp[i][j] = dp[i - 1][j];
			
			
		}
	}

	for (int i = 0; i <= sum; i++)
	{
		if (dp[N][i] >= M)
		{
			cout << i << "\n";
			break;
		}	
	}


}