[JAVA]백준 7579번: 앱

www.acmicpc.net/problem/7579

7579번: 앱

1. 문제 설명

 

N개의 앱이 활성화되어있고 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있고, 앱 Ai를 비 활성하는 비용은 ci라고 하자. M 바이트 이상의 메모리를 추가로 확보하려고 할 때 비용 ci의 합의 최솟값을 구하는 문제이다.

 

2. 풀이

 

다이나믹 프로그래밍을 이용하여 풀 수 있다.

 

 

cost[x] = 비용의 합이 X일 때, 추가로 확보할 수 있는 최대 메모리 = Math.min(cost [x], cost [x-memoryList[1][x]]+memoryList[0][x]) (memoryList[1][x] : 비용, memoryList[0][x] : 메모리)

 

문제에서 앱의 개수 (1 <=N <=100), 비용 ci(0 <=ci <=100)으로 주어졌기에 가능한 최대 비용의 합은 10000이다. 

따라서 dp배열을 10000개의 인덱스를 가진 int 배열로 선언하였다.

 

답을 구할 때 주의할 점은 M 바이트 이상이라는 점이다.

 

비용이 0 ~ 10000 중 추가로 확보할 수 있는 최대 메모리가 M 바이트 이상이며 최솟값인 비용을 찾아 정답으로 출력하면 된다.

 

 

3. 코드

 

// JAVA 11, 시간 148ms, 메모리 14704KB

import java.io.*;
import java.util.*;

public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int appNum,needMemory;
        int[][] memoryList;
        int costMAX = 10000;
        
        // x비용을 사용했을 때 최대 확보할 수 있는 메모리 바이트
        int[] cost = new int[costMAX + 1];
        int answer = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        appNum = Integer.parseInt(st.nextToken());
        needMemory = Integer.parseInt(st.nextToken());


        memoryList = new int[2][appNum];

        Arrays.fill(cost, -1);
        cost[0] = 0;

        // 비용 & 메모리 저장
        for (int x = 0; x < 2; x++) {
            st = new StringTokenizer(br.readLine());

            for (int y = 0; y < appNum; y++) {
                memoryList[x][y] = Integer.parseInt(st.nextToken());
            }
        }

        
        for (int x = 0; x < appNum; x++) {
            for (int y = costMAX; y >= memoryList[1][x]; y--) {
                if (cost[y - memoryList[1][x]] != -1) {
                    cost[y] = Math.max(cost[y], cost[y - memoryList[1][x]] + memoryList[0][x]);
                }
            }
        }

        // M 바이트 이상 확보하기 위한 최소 비용 계산
        for(int x=0;x<=costMAX;x++){
            if (cost[x] >= needMemory) {
                answer = x;
                break;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        
    }



}