문제 풀이 - 도시락 데우기(JAVA)

지식 저장소·2021년 12월 1일

코딩테스트

목록 보기

20/29

풀이

우리가 해결해야 하는 것을 정의해 봅시다. 한 도시락을 먹을 때까지 걸리는 시간은 지금까지 데운 모든 도시락을 데우는 시간의 합에 이 도시락을 먹는데 걸리는 시간을 더한 것입니다. 우리는 그중 가장 큰 값(제일 늦게 다 먹는 도시락)을 최소화하려고 합니다. 다음과 같이 쓸 수 있습니다.

$\max_{i=0}^{n-1}(e_{p[i]}+\sum_{j=0}^i m_{p[j]})$

이때 $P$ 는 {0, 1, 2, $\cdots$ , $n$ - 1}의 순열로, 각 도시락을 데우는 순서를 나타냅니다.

탐욕적 알고리즘의 구상

좀더 단순한 형태의 문제를 고려해 보면 답의 구조를 짐작할 수 있습니다. 모든 도시락을 먹는 데 같은 시간 $C$ 가 걸린다고 먼저 가정해 봅시다. 그러면 어떤 순서로 도시락을 데우건 점심 시간의 길이는 모든 도시락을 데우는 시간과 도시락 하나를 먹는 시간의 합 $C + \sum m_i$ 이란 것을 알 수 있습니다. 마지막에 데우는 도시락을 결국 마지막에 먹게 될 테니까요.
즉, 데우는 시간과는 관련 없이 먹는데 오래 걸리는 도시락부터 데우는 것이 정답입니다.

탐욕적 선택 속성 증명

도시락 목록이 주어질 때, 먹는 데 가장 오래 걸리는 $A$ 도시락을 제일 먼저 데우는 최적해가 반드시 하나는 있음을 보여 주면 됩니다. 이를 위해 다른 $x$ 번째에 데우는 $B$ 도시락을 제일 먼저 데우는 최적해가 존재한다고 가정합니다.
이 최적해에서 둘의 위치를 바꾼 뒤 이것도 최적해가 된다는 것을 보이도록 합시다. 유의할 부분은 $B$ 와 $A$ 의 순서를 바꾼다 해도, $x$ +1번 이후의 도시락들 입장에선 다를 것이 없다는 점입니다. 어느 순서로 데우건 이 도시락들이 기다려야 하는 시간은 같으니까요. 따라서 먹는 데까지 걸리는 시간이 달라지는 도시락들은 $A$ 까지, 그러니까 0번부터 $x$ 번까지의 도시락들입니다. 따라서 나머지를 무시하고 이들만을 고려하기로 합시다.
이때 이들 중 가장 마지막에 식사가 끝나는 도시락은 $A$ 라는 것을 주목합시다. 이 중 가장 늦게 데우는데다 먹는데 오래 걸리기까지 하기 때문입니다. $A$ 도시락을 먹는 사람이 식사가 끝나는 시간은 0번부터 $x$ 번까지의 도시락을 데우는 시간과 $A$ 를 먹는데 걸리는 시간의 합입니다.

$max = e_{p[x]}+\sum_{i=0}^x m_{p[i]}$

이제 남은 도시락들의 순서를 자유롭게 바꾼다고 가정합시다. 어떤 도시락도 다 먹는데 걸리는 시간이 앞에서 설명한 $max$ 를 초과할 수 없습니다. 이 순서에서 $y$ 번째 도시락을 먹는 데 걸리는 시간은 다음과 같이 쓸 수 있습니다.

$e_{p[y]}+\sum_{i=0}^y m_{p[i]}$

$y$ 번째 도시락은 $A$ 보다 먹는 데 오래 걸리지 않을 테고( $e_{p[x]}\ge e_{p[y]}$ ), 더 오래 기다려야 하는 것도 아니기 때문에( $\sum_{i=0}^x m_{p[i]}\ge\sum_{i=0}^y m_{p[i]}$ ) 이 식이 $max$ 보다 클 수는 없습니다. 따라서 $A$ 와 $B$ 의 순서를 서로 바꾼 답이 최적해보다 나빠질 수는 없고, 따라서 이 답도 최적해라는 것을 알 수 있습니다.

최적 부분 구조 증명

첫 번째 도시락을 정하고 나면 나머지 도시락들을 배치해야 합니다. 이때 각 도시락을 다 먹기까지 걸리는 시간은 첫 번째 도시락을 데우는 시간만큼 지연되지만, 남은 도시락들에 대해서도 가장 늦게 다 먹는 시간을 최소화해서 손해 볼 것은 없습니다. 따라서 매 단계마다 최적의 선택을 해도 상관 없다는 사실을 알 수 있습니다.

구현

import java.util.*;

public class Main {

    public static int N;
    public static int[] M, E;
    public static int result;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        M = new int[N];
        E = new int[N];
        for (int i = 0; i < N; i++) {
            M[i] = scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            E[i] = scanner.nextInt();
        }
    }

    public static void solve() {
        result = heat();
    }

    // 도시락을 다 먹는 시간의 최솟값을 반환하는 메소드
    public static int heat() {
        // 도시락의 먹는 시간과 인덱스를 같이 사용하기 위해 지역 클래스를 정의한다.
        class Temp implements Comparable {
            int index;
            int e;

            Temp(int index, int e) {
                this.index = index;
                this.e = e;
            }

            @Override
            public int compareTo(Object o) {
                Temp t = (Temp) o;
                return t.e - this.e;
            }
        }
        // 어느 순서로 데워야 할지를 정한다.
        ArrayList<Temp> order = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            order.add(new Temp(i, E[i]));
        }
        Collections.sort(order);
        // 해당 순서로 데워먹는 과정을 시뮬레이션한다.
        int result = 0, beginEat = 0;
        for (int i = 0; i < N; i++) {
            int box = order.get(i).index;
            beginEat += M[box];
            result = Math.max(result, beginEat + E[box]);
        }
        return result;
    }

    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}