[BOJ/Java] 7579. 앱

📌 [BOJ/Java] 7579. 앱

🔗 문제 링크: 백준 7579번 - 앱

---

📖 문제 해석

📱 여러 개의 앱이 실행 중이며, 이를 종료하거나 일부 비활성화하여 M 바이트 이상의 메모리를 확보하는 최소 비용을 구하는 문제이다.
💰 앱을 비활성화할 때 **비활성화 비용(추가 배터리 소비 등)**이 존재하며,
🛠️ 최소한의 비용으로 M 바이트 이상 확보해야 한다.

✅ 핵심 개념

• **부분 배낭 문제(0/1 Knapsack)**과 유사
• 최적의 앱 비활성화 조합을 찾는 DP 활용
• 비용(cost)을 기준으로 최소 비용으로 M 바이트 확보하도록 최적화

---

🛠️ 풀이 과정

1️⃣ 입력 처리 및 초기화

• N개의 앱의 **메모리 사용량(memory[])**과 **비활성화 비용(cost[])**을 입력받는다.
• dp[c]를 사용하여 비활성화 비용이 c일 때 확보할 수 있는 최대 메모리를 저장한다.
• **최대 비용(C)**을 계산하여 dp 배열을 크기 C + 1로 생성

2️⃣ 0/1 Knapsack 방식으로 DP 갱신

• 앱을 하나씩 고려하며, 뒤에서부터 비용을 확인하면서 DP 갱신
• dp[j] = max(dp[j], dp[j - cost[i]] + memory[i])
• 비용 j를 현재 앱의 cost[i]보다 크거나 같은 값부터 처리해야 중복 사용 방지 가능

3️⃣ M 바이트 이상 확보할 수 있는 최소 비용 찾기

• dp[j] >= M을 만족하는 최소 j를 출력

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt(); // 앱 개수
        int M = sc.nextInt(); // 확보해야 할 메모리
        int[] memory = new int[N]; // 앱 메모리 사용량
        int[] cost = new int[N]; // 앱 비활성화 비용
        int sumCost = 0;

        for (int i = 0; i < N; i++) {
            memory[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            cost[i] = sc.nextInt();
            sumCost += cost[i]; // 최대 비용 계산
        }

        int[] dp = new int[sumCost + 1]; // 비용 별 최대 확보 가능 메모리 저장
        Arrays.fill(dp, 0);

        for (int i = 0; i < N; i++) { // 각 앱에 대해 DP 갱신
            for (int j = sumCost; j >= cost[i]; j--) { // 뒤에서부터 업데이트
                dp[j] = Math.max(dp[j], dp[j - cost[i]] + memory[i]);
            }
        }

        // M 이상의 메모리를 확보할 수 있는 최소 비용 찾기
        for (int j = 0; j <= sumCost; j++) {
            if (dp[j] >= M) {
                System.out.println(j);
                break;
            }
        }
    }
}

---

⏱️ 시간 복잡도 분석

📌 O(N × C) (최대 100 × 10000 = 100만 연산)
💡 dp[j]를 갱신하는 과정이 O(N × C)이므로 충분히 해결 가능

---

💡 느낀점

✅ 배낭 문제(0/1 Knapsack)와 유사한 문제였으며,

• 배열을 비용(cost) 기준으로 갱신하는 방식을 익힐 수 있었다.
• 메모리를 기준으로 하지 않고, 비용을 기준으로 DP를 구성하는 점이 차이점

✅ 앱을 하나씩 고려하면서 뒤에서부터 업데이트하는 방식이 핵심이었다.
✅ 비용이 최소한으로 유지되도록 DP 배열을 최적화하는 전략을 다시 복습할 수 있었다. 🚀