골드 3
어플의 수 N 필요한 여유공간 M이 주어지며, 1번째 줄은 각 어플의 메모리 m[i], 2번째 줄은 각 어플이 다시 실행될 때의 비용인 c[i]가 주어진다.
5 60
30 10 20 35 40
3 0 3 5 4
1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000
M ≤ m1 + m2 + ... + mN // 항상 답이 존재한다.
...
필요한 메모리와 접근할 index를 이용하여 dp로 접근하려 했다.
index가 0부터 i사이에 있는 어플을 종료하여, 잔여 memory가 j일때 드는 cost의 최솟값
를 dp[i][j]로 정의하면
dp[i, mem] = min(c[i] + dp[i + 1, mem - m[i]], dp[i, mem])
로 정의가능하다.
dp의 범위를 결정할 때, dp[100][10000000]
로 선언하게 된다.
여기서 dp[100][10000000]
에 드는 메모리는 1GB로 메모리초과가 나게 된다!
남은 메모리 크기로 접근하면 메모리 초과가 나게 되니 다른 기준을 세워야 할 것 같다.
N의 최대값은 100이고 cost의 최대값이 100이니 최대 cost의 합은 10000이다!
dp[100][10000]정도면 충분히 통과할 수 있을 것 같다!
dp를 인덱스와 cost의 총합의 범위로 정의했으니 dp의 의미를 만들자.
index가 0부터 i사이에 있는 어플을 종료하여, 최대 cost가 j일 때 확보할 수 있는 memory 최대값
로 정의하자!
dp[i][use_c] = max(dp[i - 1][use_c], m[i] + dp[i - 1][use_c - c[i]])
여기서 우리는 memory의 최대값을 구하는 게 아닌, cost의 최소값을 구해야 한다!
따라서 M보다 작지 않은 dp의 값 중, cost가 최소인 dp를 찾아야 한다.
while (cnt(N - 1, i) >= M)
i--;
#include <iostream> #include <cstring> #include <cmath> #define MAX 10000000 using namespace std; int N, M; int m[100]; int c[100]; int dp[100][10001]; void App(); int cnt(int, int); int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); App(); } void App() { memset(dp, -1, sizeof(dp)); cin >> N >> M; for (int i = 0; i < N; i++) cin >> m[i]; for (int i = 0; i < N; i++) cin >> c[i]; int i = 10000; while (cnt(N - 1, i) >= M) i--; cout << i + 1 << '\n'; } int cnt(int idx, int use_c) { if (use_c < 0) return -MAX; if (idx < 0) return 0; int &ref = dp[idx][use_c]; if (ref != -1) return ref; return ref = max(cnt(idx - 1, use_c), m[idx] + cnt(idx - 1, use_c - c[idx])); }```