[백준 7579] 앱 (C++)

먼저, 모든 경우의 수를 따져보면, $N \le 100$이므로 최대 $2^{100}$가지의 경우가 있다는 것을 알 수 있다.

따라서, brute-force나 백트래킹으로는 절대 풀 수 없는 문제임이 확실하다.

그렇다면, 메모리 M를 확보하는데 필요한 최소 비용을 어떻게 구할 수 있을까?

단순하게 정렬로 문제가 해결되는 지 확인해보자.

용량이 부족하면 최소 비용인 것들 순서로 앱을 종료해나가면, 결과적으로 비용이 최소임이 보장되는 지 확인해봐야한다.

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

위의 경우에서, 정렬해서 접근하면 비용이 6이 되는데 최소 비용은 5이므로, 그리디로 접근하면 안된다는 것을 확인할 수 있다.

parametric-search라기엔, 가능한 모든 경우를 메모리에 담아야하기 때문에, 메모리 초과로 불가능한 풀이이다. 따라서, dp가 적절해보인다.

메모리 M만큼 확보할 때, 최소 비용을 구해야하지만, 그렇게 메모리에 대한 최소 비용으로 생각하면 비효율적이다.
일부 메모리는 확보할 수 없을 수 있어 비용을 구할 수 조차 없고, 한 번 루프를 도는데 최대 $10^7$번 연산이 될 것이기 때문이다.

따라서, 비용에 따른 확보 가능한 최대 메모리를 구하는 것이 좋다.

이렇게 관점을 바꾸면, 비용 k에 대한 최대 메모리를 구하는 것이므로 배낭 문제로 접근할 수 있어진다.

i번째 앱에서 비용 j에 대한 확보 가능한 최대 메모리를 d[i][j]라 하자.

이때, d[i][j]는 d[i - 1][j] 또는 d[i - 1][j - c[i]] + m[i]가 된다.

단, j - c[i]가 0보다 큼이 보장 되어야 d[i - 1][j - c[i]] + m[i]가 d[i][j]가 될 수 있기 때문에, 이를 유의해서 코드를 작성해야한다.

#include <bits/stdc++.h>
using namespace std;

int N, M, tot;
int m[101], c[101], d[101][10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> m[i];
	for (int i = 1; i <= N; i++) {
		cin >> c[i];
		tot += c[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= tot; j++) {
			if (j - c[i] >= 0) d[i][j] = max(d[i - 1][j], d[i - 1][j - c[i]] + m[i]);
			else d[i][j] = d[i - 1][j];
		}
	}

	for (int i = 0; i <= tot; i++) {
		if (d[N][i] >= M) {
			cout << i;
			break;
		}
	}
}