[백준 C++] 7579 앱 - 다이나믹프로그래밍

7579번: 앱

#include <iostream>
using namespace std;

int Memory[101];
int Cost[101];
int DP[101][10001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		cin >> Memory[i];
	}
	for (int i = 1; i <= N; ++i)
	{
		cin >> Cost[i];
	}

	for (int i = 1; i <= N; ++i)
	{
		int Mem = Memory[i];
		int Cst = Cost[i];
		for (int c = 0; c <= 10000; ++c)
		{
			if (c >= Cst)
			{
				DP[i][c] = max(DP[i - 1][c], DP[i - 1][c - Cst] + Mem);
			}
			else
			{
				DP[i][c] = DP[i - 1][c];
			}
		}
	}

	for (int c = 0; c <= 10000; ++c)
	{
		if (DP[N][c] >= M)
		{
			cout << c;
			return 0;
		}
	}
}

---

 

DP & 배낭 문제입니다.

 

DP[i][c]는 1번 앱부터 i번 앱까지 각 앱을 선택 혹은 미선택하고 누적된 비용이 c일때의

확보된 메모리의 최대값을 저장하도록 했습니다.

 

N번째 앱까지 DP값을 모두 채운 후에는

DP[N][c] 에서 c(누적 비용)를 0부터 1씩 증가시키면서

처음으로 M 이상의 메모리를 확보할 수 있는 비용을 찾아서 출력하도록 했습니다.