백준 7579번 [앱](C++) -yes6686- 티스토리

백준 문제 풀이: 7579 [앱]

---

문제 링크: https://www.acmicpc.net/problem/7579

문제 설명:

여러 앱이 실행 중이며, 각 앱은 특정 메모리를 사용하고 있습니다. 메모리를 확보하기 위해 일부 앱을 종료해야 하는데, 이를 위해 앱마다 비용이 부과됩니다. 최소 비용으로 지정된 메모리 이상의 공간을 확보하려면 어떤 앱을 종료해야 할까요?

---

문제 해결 코드

#include <iostream>
using namespace std;

int arrm[101]; // 앱의 메모리 사용량
int arrc[101]; // 앱의 종료 비용
int dp[10001]; // dp[j]: j 비용으로 확보 가능한 최대 메모리
int sum[10001]; // 비용의 누적합

int main() {
    int n, m;
    cin >> n >> m; // 앱의 개수와 확보해야 하는 메모리
    for (int i = 1; i <= n; i++) {
        cin >> arrm[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> arrc[i];
        sum[i] = sum[i - 1] + arrc[i];
    }

    int result = 10001; // 최소 비용을 구하기 위한 초기값 설정
    for (int i = 1; i <= n; i++) {
        for (int j = sum[i - 1]; j >= 0; j--) {
            if (dp[j] < m) {
                dp[arrc[i] + j] = max(dp[arrc[i] + j], arrm[i] + dp[j]);
                if (dp[arrc[i] + j] >= m) {
                    result = min(result, arrc[i] + j);
                }
            }
        }
    }

    if (result == 10001) {
        cout << 0;
    } else {
        cout << result;
    }
}

예제

입력:
5 60
30 10 20 35 40
3 0 3 5 4

출력:
6

---

코드 설명

• 입력 처리: 각 앱의 메모리 사용량과 종료 비용을 배열로 저장합니다.
• DP 배열 업데이트:
  • 비용이 증가함에 따라 확보 가능한 메모리를 dp 배열에 기록합니다.
  • dp[j]는 j 비용으로 확보 가능한 최대 메모리를 나타냅니다.
• 결과 계산: 목표 메모리 이상을 확보하는 최소 비용을 result 변수에 저장합니다.

시간 복잡도

• 외부 반복: O(n) (앱의 개수)
• 내부 반복: O(sum[i]) (비용의 누적합)
• 총 시간 복잡도: O(n × max 비용)

결과

위 코드는 최소 비용으로 지정된 메모리를 확보하는 방법을 효율적으로 계산합니다.