앱 (feat. 백준, 7579번)

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

7579번: 앱

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, sum = 0, ans = 0;
	int A[101]{ 0 }, c[101]{ 0 }, dp[101][100 * 100 + 1]{ 0 };
	cin >> N >> M;
	for (register int n = 1; n <= N; ++n)
		cin >> A[n];
	for (register int n = 1; n <= N; ++n)
		cin >> c[n], sum += c[n];
	for (register int i = 1; i <= N; ++i)
		for (register int j = 0; j <= sum; ++j){
			if (j - c[i] >= 0)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + A[i]);
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	while (true)
		if (dp[N][ans++] >= M)
			break;
	cout << ans - 1;
	return 0;
}
// *&)*@*

1. N개의 앱과 메모리 바이트를 2차원 배열 형태로 dp를 생성합니다. 그리고 dp의 값은 메모리 값 입니다. (dp[0][0] = 메모리값)
2. 1 ≤ N ≤ 100 이므로 dp[101], 0 ≤ c1, ..., cN ≤ 100 이므로 dp[100 * 100 + 1]. 즉, dp[101][100 * 100 + 1] 이 총 크기가 됩니다.
3. 예제를 dp로 표현하면 아래와 같습니다.

dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + A[i]) 가 dp 계산의 핵심입니다.