백준 7579 앱 java

문제 소개 www.acmicpc.net/problem/7579

내용

우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 

대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 

새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다.

이러한 과정을 앱의 ‘비활성화’라고 한다.

앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다

 

현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자.

이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자.

이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자.

여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

입력

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다

 

단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.

출력

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다. 

해결 방법

아이디어

첫번째 아이디어

app을 비활성화 하는 모든 경우의 수에서 m보다 메모리가 큰 것 중에 cost의 합이 가장 작은 것을 찾는 방법이다.

n이 100이므로 모든 경우의 수에서 100! 가지 수가 나와 시간초과가 날 것이라고 생각했다.

두번째 아이디어

행렬 곱 문제에서의 카탈란 수 계산처럼 각 영역을 계산한 뒤 m보다 메모리가 큰 것 중 cost의 합이 가장 작은 것을 찾는 방법을 생각했다. n^2의 반복이면 된다. 시간은 초과하지 않는다. 하지만 영역은 연속된 부분들이다. 만약 m이 80이고 배열이 10 20 30 40 이면 10 30 40 을 골라야하는데 이러한 경우가 있으므로 적합하지 않은 아이디어다.

검색한 정답

배낭 문제 알고리즘으로 해결하였다. 배낭문제와 비슷하다는 느낌도 받긴하였으나 코드로 바꾸지 못했다. 

dp[n][n*maxCost(100001)] 만큼 생성한다. dp배열의 각 배열에서 칼럼의 값이 cost가 되며 저장되는 value는 해당 코스트로 만들어지는 최대 메모리값이다. 

 

실제 풀이 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        int n = Integer.parseInt(split[0]);
        int m = Integer.parseInt(split[1]);

        int[] activeAppMemories = new int[n];
        int[] reactiveAppCosts = new int[n];

        String[] memoriesData = br.readLine().split(" ");
        String[] costsData = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            activeAppMemories[i] = Integer.parseInt(memoriesData[i]);
            reactiveAppCosts[i] = Integer.parseInt(costsData[i]);
        }

        int[][] dp = new int[n][100001];

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int cost = reactiveAppCosts[i];
            int memory = activeAppMemories[i];

            for (int j = 0; j <= 10000; j++) {
                if (i == 0) {
                    if (j >= cost) dp[i][j] = memory;
                } else {
                    if (j >= cost) dp[i][j] = Math.max(dp[i - 1][j - cost] + memory, dp[i - 1][j]);
                    else dp[i][j] = dp[i - 1][j];
                }

                if (dp[i][j] >= m) answer = Math.min(answer, j);
            }
        }

        System.out.println(answer);
    }
}

결과

배낭 알고리즘 dp를 코드로 생각을 잘 못하는 것 같다. 연습을 해봐야겠다.