[C++] 백준 7579: 앱

문제 이해

- 현재 N개의 앱, A1, ..., An이 활성화 되어있다.

- 이들 앱은 각각 mi바이트만큼 메모리를 사용한다.

- 각 앱을 다시 실행하고자 할 때 ci의 비용이 들어간다.

- N개의 앱 중 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 확보하고자 할 때, 비용 ci의 합을 최소화하는 방법을 구하라.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 128MB

 

<입력>

- N: 활성화된 앱의 개수 (1 ~ 100, 10^2)

- M: 필요한 메모리의 크기 (1 ~ 10,000,000, 10^7)

- mi: Ai가 사용중인 메모리의 바이트 크기 (1 ~ 10,000,000, 10^7)

- ci: Ai를 비활성화 했을 때 비용 (0 ~ 100, 10^2)

※ M <= m1 + ... mn이다.

 

<출력>

- 필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소 비용을 계산하라.

 

 

 

문제 풀이

문제를 이해하고나서 DP 중에서도 배낭 문제처럼 풀어야겠다는 생각이 들었다.

 

 

 

일단 dp[i][j]를 정의하는 것이 중요했는데,

 

 

만약 i를 앱의 종류, j를 메모리의 크기로 했을경우

앱의 종류의 최댓값이 10^2, 메모리의 최댓값이 10^7으로

2차원 배열을 구성했을 때 메모리 초과가 날 수 밖에 없었다.

 

 

 

그렇기에 j를 다른 것으로 둘 필요가 있었는데 바로 '비용'이다.

 

비용의 최댓값은 100이므로 합의 최댓값도 100 * 100인 10,000이다.

이 경우 제한된 메모리 안에서 구현할 수 있게 된다.

 

 

 

dp[i][j]: i번째 앱까지 확인했을 때, j의 비용으로 얻을 수 있는 최대의 메모리

라고 정의하자.

 

 

 

이 경우, j가 늘어날수록 사용할 수 있는 메모리가 커질텐데

이 메모리가 M 이상이 되었을 때의 비용을 답으로 출력하면 된다.

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

int n, m, sum = 0;
int dp[105][10101];
int mem[105];
int cost[105];

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

    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>mem[i];
    }
    for(int i = 1; i <= n; i++){
        cin>>cost[i];
        sum += cost[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= sum; j++){
            if(j >= cost[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]] + mem[i]);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

    for(int i = 0; i <= sum; i++){
        if(dp[n][i] >= m){
            cout<<i;
            break;
        }
    }
    
    return 0;
}

 

 

 

배운 점

- dp배열의 값을 항상 문제에서 원하는 값으로 설정하는 경우가 많았는데, 이 문제는 아니었다.

- 위와 같은 케이스 문제도 잘 숙지해보도록 하자.