백준 7579 앱 [c++]

25 Jun 2022 in Develop / Solving

c++

문제 분석

• 문제 길어….
• 여러 개의 앱이 활성화 되어 있는데, 이 중 일부 앱을 꺼서, 일정량 이상의 메모리를 확보하려고 한다.
• 각각의 앱은 정해진 크기의 메모리를 차지하고 있으며,
• 프로그램을 끌 때도 프로그램별로 일정 비용이 필요하다.
• 최소 비용으로 일정량 이상의 메모리를 확보하게 해 봐라.

입력조건

켜져 있는 프로그램 수 N 확보해야 할 메모리 양 M
N개의 프로그램이 차지하는 메모리 양 [숫자]
N개의 프로그램을 끌 때 필요한 비용 [숫자]

풀이과정

• 가방 문제…
• 백트래킹으로 풀었다가 시간초과를 봐버렸다.
• dp로 배낭문제처럼 dp판을 완성한 뒤,
• dp의 맨 밑줄에서 M보다 크거나 같아지는 최초의 값을 출력.

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    int *memories;
    int *shutcost;

    cin >> N >> M;

    memories = new int[N+1];
    shutcost = new int[N+1];
    int costsum = 0;

    for(int i = 1; i <= N; i++) cin >> memories[i];
    for(int i = 1; i <= N; i++) {
        cin >> shutcost[i];
        costsum += shutcost[i];
    }

    int dp[N+1][costsum + 1];
    
    for(int i = 0; i <= costsum; i++) dp[0][i] = 0;

    for(int i = 1; i <= N; i++ ) {
        for(int j = 0; j <= costsum; j++) {
            dp[i][j] = 0;

            if( j - shutcost[i] >= 0 ) 
                dp[i][j] = dp[i-1][j-shutcost[i]] + memories[i];

            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

    // for(int i = 0; i <= N; i++) {
    //     for(int j = 0; j <= costsum; j++){
    //         printf("%4d", dp[i][j]);
    //     }
    //     cout << endl;
    // }

    for(int i = 0; i <= costsum; i++) {
        if(dp[N][i] >= M) {
            cout << i << endl;
            return 0;
        } 
    }
}