[백준 7579번 C/C++] 앱

 

[백준 7579번 C/C++] 앱

 

https://www.acmicpc.net/problem/7579

7579번: 앱

---

 

해결전략

 

Dynamic Programming 다이나믹 프로그래밍, 동적 계획법

배낭

 

---

 

해설

 

dp[ i ][ j ]  

dp[ i ][ j ] = i개 이하의 메모리 앱을 사용하고, j 이하의 비용으로 확보할 수 있는 최대 메모리 크기

i  \  j
1	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
2	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
3	10	10	40	40	40	60	60	60	60	60	60	60	60	60	60
4	10	10	40	40	45	60	60	75	75	75	95	95	95	95	95
5	10	10	40	50	50	60	80	80	85	100	100	115	115	115	135

i는 비활성할 메모리 앱의 수

j는 비활성하여 확보한 메모리

 

 

dp[ i ][ j ] = max (dp[ i - 1 ][ j ], dp[ i - 1 ][ j - cost[ i ]] + memory[ i ])

 

 

---

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m; // n은 메모리 수, m은 필요한 메모리 바이트
vector<int> memory, cost; // memory[i]는 해당 앱의 메모리, cost[i]는 해당 앱의 비용
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    memory.resize(n+1); // 앱의 메모리 정보를 저장할 배열
    cost.resize(n+1);   // 앱의 비용 정보를 저장할 배열
 
    // 각 앱의 메모리 정보를 입력받아 저장
    for (int i = 1; i <= n; i++)
        cin >> memory[i];
 
    int totalCost = 0; // 모든 앱의 비용의 합을 저장할 변수
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        totalCost += cost[i];
    }
 
    // dp[i][j] = i개 이하의 메모리 앱을 사용하고, j 이하의 비용으로 확보할 수 있는 최대 메모리 크기
    vector<vector<int>> dp(n + 1, vector<int>(totalCost + 1, 0));
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= totalCost; j++) {
            if (j >= cost[i])
                // 현재 앱을 선택할 수 있는 경우와 선택하지 않는 경우 중에서 최대 메모리 크기 선택
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
            else
                // 현재 앱의 비용이 선택 가능한 비용보다 크면 선택하지 않음
                dp[i][j] = dp[i - 1][j];
        }
    }
 
 
   //디버깅
    cout << "\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= totalCost; j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
 
 
 
    int answer = 0;
    // 필요한 메모리 크기인 m보다 크거나 같은 최소 비용을 찾아 answer에 저장
    for (int j = 0; j <= totalCost; j++) {
        if (dp[n][j] >= m) {
            answer = j;
            break;
        }
    }
 
    cout << answer << "\n";
 
    return 0;
}

 

 

 

 

---