[JAVA] 백준 (골드3) 7579번 앱

링크

https://www.acmicpc.net/problem/7579

---

입력 예제

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

---

출력 예제

6

---

풀이

주어진 앱을 비활성화 함으로써 메모리 M 이상을 확보했을 때의 최소 비용을 구해야 한다. dp 배열을 비용을 기준으로 최대 메모리를 저장하여 메모리가 M 이상일 때의 최소 비용을 구한다. 이때 배열의 크기는 비용의 총합 + 1 으로 설정한다.

int[] dp = new int[sumCost + 1];  //dp[i]: 비용 i로 얻을 수 있는 최대 메모리

모든 앱을 탐색하면서 dp 배열을 갱신해간다. 이때 배낭 문제는 모든 아이템에 대하여 한 번씩만 사용하기 위해 역방향으로 갱신해야 한다.

for (int i = 0; i < N; i++) {  //모든 앱에 대하여 탐색
    int curM = memory[i];
    int curC = cost[i];
    
    //현재 앱을 비활성화함으로써 최대 메모리 갱신
    for (int j = sumCost; j >= curC; j--) {
        //dp[j - curC]: 현재 앱을 비활성화 하기 전의 최대 메모리
        dp[j] = Math.max(dp[j], dp[j - curC] + curM);
    }
}

전체 코드

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

/*
백준 / 앱 / 골드3
https://www.acmicpc.net/problem/7579
 */
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[] memory = new int[N];
        int[] cost = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {  //활성화 된 앱의 메모리
            memory[i] = Integer.parseInt(st.nextToken());
        }

        int sumCost = 0;  //비용 총합
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {  //비활성화 했을 경우 비용
            cost[i] = Integer.parseInt(st.nextToken());
            sumCost += cost[i];
        }

        int[] dp = new int[sumCost + 1];  //dp[i]: 비용 i로 얻을 수 있는 최대 메모리

        for (int i = 0; i < N; i++) {  //모든 앱에 대하여 탐색
            int curM = memory[i];
            int curC = cost[i];

            //현재 앱을 비활성화함으로써 최대 메모리 갱신
            for (int j = sumCost; j >= curC; j--) {
                //dp[j - curC]: 현재 앱을 비활성화 하기 전의 최대 메모리
                dp[j] = Math.max(dp[j], dp[j - curC] + curM);
            }
        }

        //메모리가 M이상인 최소 비용 탐색
        for (int i = 0; i <= sumCost; i++) {
            if (dp[i] >= M) {
                System.out.println(i);
                return;
            }
        }
    }
}