[BOJ] 7579 앱

링크

BOJ 7579

난이도

골드 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 // 항상 답이 존재한다.
...

문제 접근 1

필요한 메모리와 접근할 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로 메모리초과가 나게 된다!

문제 접근 2

남은 메모리 크기로 접근하면 메모리 초과가 나게 되니 다른 기준을 세워야 할 것 같다.

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]));
}```