7579 - 앱 (Java)

스마트폰에서는 백그라운드에 활성화된 앱들이 메모리에 남아 있어,
앱을 재실행할 때 빠르게 복원할 수 있지만 메모리가 한정적입니다.
새 앱을 실행하려면 추가로 필요한 메모리를 확보하기 위해 일부 앱을 비활성화해야 합니다.

---

1️⃣ 문제 요약

• 활성화된 앱 개수 N (최대 100)
• 확보해야 할 메모리 M (최대 10,000,000 바이트)
• 앱 i를 비활성화하면
  • 확보되는 메모리: memory[i] 바이트
  • 추가로 드는 비용: price[i] (0~100)
• 전체 확보 메모리 ≥ M 이 되도록
• 비용 총합을 최소화

---

2️⃣ 첫 시도: 메모리 기준 DP 🐌

• 전형적인 0/1 배낭처럼 dp[i][mem]으로 잡으면
  • mem 최대 10,000,000 → dp 크기 약 100 × 10,000,000 = 1,000,000,000
  • 메모리·시간 모두 불가능 ❌

---

3️⃣ 비용 기준 DP로 전환 💡

아이디어: DP의 두 번째 차원을 ‘비용 합(cost)’으로 바꾼다!

• 앱 하나당 비용 ≤ 100 → 최대 비용 합 = 100 × N ≤ 10,000
• DP 배열 크기 100 × 10,000 = 1,000,000 → 충분히 처리 가능

DP 상태

dp[i][cost] = "앱 1..i를 고려했을 때, 비용 합이 cost일 때 확보할 수 있는 최대 메모리"

• 전이식
  1. 앱 i 비활성화 안 함

     dp[i][cost] = dp[i-1][cost]

  2. 앱 i 비활성화 (if cost ≥ price[i])

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

---

🛠️ 구현 포인트

int maxCost = N * 100;
int[][] dp = new int[N + 1][maxCost + 1];

// DP 테이블 채우기
for (int i = 1; i <= N; i++) {
    for (int cost = 0; cost <= maxCost; cost++) {
        // 1) 앱 i 비활성화 안 함
        dp[i][cost] = dp[i - 1][cost];
        // 2) 앱 i 비활성화
        if (cost >= price[i]) {
            dp[i][cost] = Math.max(
                dp[i][cost],
                dp[i - 1][cost - price[i]] + memory[i]
            );
        }
    }
}

// 최소 비용 찾기
int answer = Integer.MAX_VALUE;
for (int cost = 0; cost <= maxCost; cost++) {
    if (dp[N][cost] >= M) {
        answer = cost;
        break;  // 최초 발견이 최소 비용
    }
}
System.out.println(answer);

• ⏱️ 시간 복잡도: O(N × maxCost) = 약 100 × 10,000 = 1e6 → 빠르게 통과
• 💾 메모리 절약: 2차원 → 1차원 rolling array로 최적화 가능

---

🌟 느낀 점

1. DP 상태 정의를 유연하게 바꾸는 것이 관건!
2. 문제 제약에 맞춰 “기준”을 전환하면 해법이 확 열림 🔑