[백준] 7579번: 앱 (Java)

1. 문제설명

스마트폰의 메모리는 메모리 부족 상태를 방지하기 위해 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 과정을 수행한다.(비활성화)

현재 N개의 앱이 활성화 되어 있을 때, 앱 $A_i$는 각각 $m_i$ 바이트만큼 메모리를 사용한다. 앱 $A_i$를 비활성화한 후 다시 실행시키면, 추가적으로 드는 비용은 $c_i$ 이다. 새로운 앱을 실행시키면 추가로 $M$ 바이트의 메모리가 필요하고, 현재 활성화 되어 있는 앱 중 몇 개를 비활성화하여 M 바이트 이상의 메모리를 추가로 확보해야 한다.

비활성화 했을 경우의 메모리 $M$ 바이트를 확보하는 비용 $c_i$ 의 최소 비용을 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• DP 방법을 사용한다. (Knapsack 문제의 변형)
• DP 배열에 비용 j로 확보할 수 있는 최대 메모리를 저장한다. (인덱스는 비용을 나타냄)
• 각 앱에 대해 반복하면서 DP 배열을 갱신한다.
  • 각 앱을 탐색할 때 더 많은 메모리를 확보할 수 있는지 확인한다.
  • DP 배열을 역순을 탐색하여 각 앱을 한 번만 사용하도록 한다.
• 최종 DP 배열에서 필요한 메모리 M을 확보할 수 있는 최소 비용(인덱스)를 구한다.

 

3. 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 활성화 되어 있는 앱의 개수
        int M = Integer.parseInt(st.nextToken()); // 필요한 메모리 바이트

        int[] m = new int[N]; // 각 앱이 사용중인 메모리
        int[] c = new int[N]; // 각 앱이 비활성화할 때 드는 추가 비용
        int totalCost = 0; // 최대 비용, dp 배열의 크기

        String[] input = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            m[i] = Integer.parseInt(input[i]);
        }
        input = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            c[i] = Integer.parseInt(input[i]);
            totalCost += c[i];
        }

        int[] dp = new int[totalCost+1]; // 각 비용에 대한 최대 메모리 저장

        for(int i=0; i<N; i++) {
            for(int j=totalCost; j>=c[i]; j--) { // DP 배열 역순 탐색
                // 현재 앱을 비활성화하는 경우와 그렇지 않은 경우 중 최대 메모리 선택
                dp[j] = Math.max(dp[j], dp[j-c[i]] + m[i]);
            }
        }

        // 필요한 메모리 M을 확보할 수 있는 최소 비용 찾음
        for(int i=0; i<=totalCost; i++) {
            if(dp[i] >= M) {
                System.out.println(i);
                break;
            }
        }
    }
}