[C++] 백준/Gold/7579. 앱

문제: 사이클 게임 (백준 7579번)

우리는 주어진 앱들의 메모리 사용량과 비활성화 비용을 바탕으로, 필요한 메모리 M 이상을 확보하기 위해 최소 비용을 계산해야 한다.
이 문제는 0-1 Knapsack 문제를 응용한 형태로 볼 수 있다.

핵심 아이디어

• 앱의 메모리 사용량을 배낭 문제의 "가치", 비활성화 비용을 "무게"로 해석한다.
• 목표는 최소 비용으로 M 이상의 메모리를 확보하는 것이다.
• 비용(c)을 역순으로 탐색해 중복 계산을 방지한다.
• dp[j]는 "비용이 j일 때 확보할 수 있는 최대 메모리"를 나타낸다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> apps(n + 1), costs(n + 1);
    for (int i = 1; i <= n; i++) cin >> apps[i]; // 앱의 메모리 사용량
    for (int i = 1; i <= n; i++) cin >> costs[i]; // 앱의 비활성화 비용

    vector<int> dp(10001, 0); // 비용 최대치만큼 배열 생성
    int minCost = 10001; // 최소 비용 초기화

    for (int i = 1; i <= n; i++) {
        int c = costs[i]; // 현재 앱의 비용
        int a = apps[i];  // 현재 앱의 메모리
        for (int j = 10000; j >= c; j--) { // 비용 역순 탐색
            dp[j] = max(dp[j], dp[j - c] + a); // 최대 메모리 계산
            if (dp[j] >= m) minCost = min(minCost, j); // 조건 만족 시 최소 비용 갱신
        }
    }

    cout << minCost << '\n'; // 최소 비용 출력
}

동작 방식

1. 입력받은 앱의 메모리 사용량(apps)과 비활성화 비용(costs)을 바탕으로 dp 배열을 갱신한다.
2. 비용(c)을 역순으로 탐색해 같은 앱이 중복 계산되지 않도록 한다.
3. 목표 메모리(M)를 확보한 상태에서 최소 비용을 갱신한다.
4. 최종적으로 dp[j]가 M 이상일 때의 최소 비용을 출력한다.

시간 및 공간 복잡도

• 시간 복잡도: O(nxC) (여기서C = 10000, 비용의 최대값)
• 공간 복잡도: O(C)

예제 입력 및 출력

입력:

5 60  
30 10 20 35 40  
3 0 3 5 4  

출력:

6

비용 6으로 메모리 60을 확보할 수 있다.