[백준] 7579번 - 앱 (Gold 3)

문제 링크

백준 7579번 - 앱 (Gold 3)

문제 설명

활성화 된 앱들의 메모리 $m_1, \cdots, m_N$ 과 재활성화시 들어가는 비용 $c_1, \cdots, c_N$, 추가로 확보해야하는 메모리 $M$이 주어져 있다.
메모리를 추가로 확보하면서 종료된 앱들을 재활성화할 때 드는 비용은 최소로 하고자 한다.
이 때 가능한 최소 비용을 구하는 문제이다.

정답 코드 및 설명

$m_{i_1} + \cdots + m_{i_k} \geq M$일 때 $c_{i_1} + \cdots + c_{i_k}$의 최솟값을 구하는 문제이다. 처음 내 발상은 문제를 역으로 뒤집어서, $m_{i_1} + \cdots + m_{i_k} \leq \textrm{(total memory)}-M$ 일 때 $c_{i_1} + \cdots + c_{i_k}$의 최댓값을 구하는 것이었다.
이는 앞에서 풀었던 백준 12865번 - 평범한 배낭 (Gold 5)와 정확히 일치하는 문제이며, 이렇게 풀어도 정답이 된다.

처음 푼 답안의 실행시간이 너무 길어서 다른 답안을 읽어본 결과 더 좋은 알고리즘을 찾을 수 있었다.
재활성화할 때 드는 비용의 최대치가 $c$일 때 확보 가능한 최대의 메모리를 구해서 배열 $\textrm{memory}$에 넣는다.
그러면 $\textrm{memory}[c]$가 $M$을 넘는 최소의 값 c가 $M$ 이상의 메모리를 확보하기 위한 최소 비용이다.

앱의 개수가 최대 100개이고, 각 앱의 재활성화 비용이 최대 100이므로, 총 비용은 10000을 넘을 수 없다.
이 문제에서 앱의 메모리 범위는 매우 큰 편이라, 비용을 기준으로 삼는 것이 시간 및 메모리를 줄이는데 큰 도움이 된다.

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

public class Main {

    static App apps[];
    static int n;

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

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        apps = new App[n];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int memory, price;
        for (int i = 0; i < n; i++) {
            memory = Integer.parseInt(st1.nextToken());
            price = Integer.parseInt(st2.nextToken());
            apps[i] = new App(memory, price);
        }
        bw.write(price(m) + "");
        bw.close();
    }

    static int price(int m) {
        int memory[] = new int[10001];
        int mi, pi;
        for (int i = 0; i < n; i++) {
            mi = apps[i].memory;
            pi = apps[i].price;
            // i번째 앱을 종료하는 것이 이득인지 처리
            // memory[j]를 구할 때 memory[j-pi]를 사용하므로, 뒤부터 바꿔야한다.
            for (int j = 10000; j >= pi; j--)
                if (memory[j] < memory[j - pi] + mi)
                    memory[j] = memory[j - pi] + mi;
        }
        // 메모리 m 이상을 확보하기 위한 최소 비용 구하기
        int price = 0;
        while (memory[price] < m)
            price++;
        return price;
    }
}

class App {
    int memory, price;

    App(int memory, int price) {
        this.memory = memory;
        this.price = price;
    }
}