[백준 C++] 7579번: 앱

1. 문제

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

7579번: 앱

 

2. 알고리즘 분류

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

 

3. 소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int memory_table[101];
int cost_table[101];
int dp[101][10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// N : 앱의 개수, M : 필요한 메모리 입력
	int N, M, sum_cost = 0;
	cin >> N >> M;

	// 현재 활성화 되어 있는 앱이 사용 중인 메모리량 입력
	for (int i = 1; i <= N; i++)
		cin >> memory_table[i];

	// 각 앱을 비활성화 했을 경우의 비용 입력
	for (int i = 1; i <= N; i++)
	{
		cin >> cost_table[i];
		sum_cost += cost_table[i];	// 모든 cost의 합을 계산
	}

	/* 배낭 문제(DP 활용)
	* dp[i][j] = i번째 앱까지 탐색했을 때, j 비용을 소모해서 얻을 수 있는 최대 메모리
	* case 1) 현재 j 비용보다 i번째 앱의 cost가 작을 경우
	*  - (i - 1)번째 앱에서 j 비용일 때 최대 메모리 값 기록
	* case 2) 현재 j 비용보다 i번째 앱의 cost가 크거나 같은 경우
	*  - max((i - 1)번째 앱에서 j 비용일 때 최대 메모리 값, (i - 1)번째 앱에서 (j - i번째 앱의 cost)의 최대 메모리 값 + i번째 앱의 메모리량)
	*/ 
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= sum_cost; j++)
		{
			if (j - cost_table[i] >= 0)	// case 2
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost_table[i]] + memory_table[i]);
			else  // case 1
				dp[i][j] = dp[i - 1][j];
		}
	}

	// N번째 앱에서 메모리량이 M 이상 확보가 가능한 순간의 비용을 출력
	for (int i = 0; i <= sum_cost; i++)
	{
		if (dp[N][i] >= M)
		{
			cout << i << endl;
			break;
		}
	}

	return 0;
}

 

4. 유용한 알고리즘

 1) 배낭 문제 알고리즘

  어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치 V를 가지고 있고 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제

	/* 배낭 문제(DP 활용)
	* dp[i][j] = i번째 앱까지 탐색했을 때, j 비용을 소모해서 얻을 수 있는 최대 메모리
	* case 1) 현재 j 비용보다 i번째 앱의 cost가 작을 경우
	*  - (i - 1)번째 앱에서 j 비용일 때 최대 메모리 값 기록
	* case 2) 현재 j 비용보다 i번째 앱의 cost가 크거나 같은 경우
	*  - max((i - 1)번째 앱에서 j 비용일 때 최대 메모리 값, (i - 1)번째 앱에서 (j - i번째 앱의 cost)의 최대 메모리 값 + i번째 앱의 메모리량)
	*/ 
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= sum_cost; j++)
		{
			if (j - cost_table[i] >= 0)	// case 2
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost_table[i]] + memory_table[i]);
			else  // case 1
				dp[i][j] = dp[i - 1][j];
		}
	}