[알고스팟] 도시락 데우기 (LUNCHBOX)

[알고스팟] 도시락 데우기 (LUNCHBOX)

문제 정보

시간제한 : 5000ms
메모리 제한: 65536kb

문제

After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp.
He contacted the famous packed lunch company "Doosot" to prepare N lunch boxes for N participants. Due to the massive amount of order, Doosot was not able to prepare the same menu. Instead, they provided different N lunch boxes. Ainu7 put all the lunch boxes to a refrigerator.
The lunch time has come, and suddenly Ainu7 noticed that there is only one microwave available. As all lunch boxes are not the same, they need a different amount of time to microwave and eat. Specifically, i-th lunch box needs Mi seconds to microwave and Ei seconds to eat.
Ainu7 needs to schedule microwave usage order to minimize lunch time. Lunch time is defined as the duration from the beginning of microwaving of any lunch box to the end of eating for all participants. Write a computer program that finds minimum lunch time to help Ainu7. Note that substituting lunch while microwave is turned on is totally unnecessary, because the lunch will be cooled down.

입력

The first line of the input contains one integer T, the number of test cases.
Each test case consists of three lines. The first line of each test case contains N(1≤N≤10000), the number of the participants.
N integers will follow on the second line. They represent M1, M2, ⋯, MN.
Similarly, N integers will follow on the third line, representing E1, E2, ⋯, EN.

출력

For each test case, print the minimized lunch time in one line. It is guaranteed that the answer is always strictly less than 231.

예제 입력

2
3
2 2 2
2 2 2
3
1 2 3
1 2 1

예제 출력

8
7

정답

[x] 내가 스스로 풀었음
[ ] 풀이를 참고함
[ ] 못 풀었음
package apss.ch10;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Lunchbox {

        public static int N;
        public static int[][] arr;

        public static void main(String[] args) throws NumberFormatException, IOException {
                // TODO Auto-generated method stub

                System.setIn(new FileInputStream("D://sample_input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
                int T = Integer.parseInt(br.readLine().trim());
                for(int testCase=1; testCase<=T; testCase++) {

                        N = Integer.parseInt(br.readLine().trim());
                        arr = new int\[N\][2];

                        StringTokenizer st = new StringTokenizer(br.readLine());
                        for(int i=0; i<N; i++) {
                                arr\[i\][0] = Integer.parseInt(st.nextToken());
                        }

                        st = new StringTokenizer(br.readLine());
                        for(int i=0; i<N; i++) {
                                arr\[i\][1] = Integer.parseInt(st.nextToken());
                        }

                        Arrays.sort(arr, new Comparator<int[]>() {

                                @Override
                                public int compare(int[] o1, int[] o2) {
                                        // TODO Auto-generated method stub
                                        return o2[1] - o1[1];
                                }

                        });

                        int result = greed();

                        bw.flush();
                        bw.write(result + "\n");
                }
                bw.close();

        }

        // 점심을 먹는데 걸리는 최소시간 
        public static int greed() {

                int burn = 0;
                int eat = 0;

                for(int i=0; i<arr.length; i++) {
                        burn += arr\[i\][0];
                        eat = Math.max(eat, burn + arr\[i\][1]);
                }

                return eat;

        }

}

풀이

최소화해야 할 값
한 도시락을 먹을 때까지 걸리는 시간은 지금까지 데운 모든 도시락을 데우는 시간의 합에 이 도시락을 먹는데 걸리는 시간을 더한 것. 우리는 그중 가장 큰 값을 최소화 하려고 한다. 이는 다음과 같다.

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

탐욕적 알고리즘의 구상
왠지 데우는 시간과는 관련 없이 먹는데 오래 걸리는 도시락부터 데우는 것이 정답일 것 같다.

탐욕적 선택 속성 증명
도시락의 목록이 주어질 때, 먹는데 가장 오래 걸리는 샤브샤브 도시락을 제일 먼저 데우는 최적해가 반드시 하나는 있음을 보여주면 된다? 이를 위해 다른 도시락, 예를 들어 돈까스 도시락을 제일먼저 데우는 최적해가 존재한다고 가정하자.

번호	0	…	x	x+1	…	n-1
도시락	돈까스	…	샤브샤브	…	…	…

이 최적해에서 둘의 위치를 바꾼 뒤 이것도 최적해가 된다는 것을 보이도록 하자. 유의할 부분은 돈까스와 샤브샤브의 순서를 바꾼다 해도, x+1번 이후의 도시락들 입장에선 다를 것이 없다는 점이다. 어느 순서로 데우건 이 도시락들이 기다려야 하는 시간은 같다. 따라서 먹는 데까지 걸리는 시간이 달라지는 도시락들은 샤브샤브까지, 그러니까 0번부터 x번까지의 도시락들이다. 따라서 나머지를 무시하고 이들만들 고려한다.

이때 이들 중 가장 마지막에 식사가 끝나는 도시락은 항상 샤브샤브라는 것을 주목하자. 이 중 가장 늦게 데우는데다 먹는 데 오래 걸리기까지 하기 때문이다. 샤브샤브를 먹는 사람이 식사가 끝나는 시간은 0번부터 x번까지의 도시락을 데우는 시간과 샤브샤브를 먹는 데 걸리는 시간의 합이다.

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

y번째 도시락은 샤브샤브보다 먹는데 오래 걸리지 않을 테고

더 오래 기다려야 하는 것도 아니기 때문에

이 식이 max보다 클 수는 없다. 따라서 샤브샤브와 돈까스의 순서를 서로 바꾼 답이 최적해 보다 나빠질 수는 없고, 따라서 이 답도 최적해라는 것을 알 수 있다?

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

회고

풀이에서 샤브샤브와 돈까스의 순서를 서로 바꾼 답이 최적해보다 나빠질 수는 없기때문에 이 답도 최적해라고 했다(?표시). 이부분이 잘 이해가 안되는데, 그렇다면 샤브샤브가 꼭 맨앞에 있지 않은 더 시간이 짧은 답이 존재한다는 것인가? 그렇다면 시간이 오래걸리는 도시락을 제일 앞에 배치하는게 꼭 답이 될 수는 없다는 것을 의미하는 것은 아닐까?

https://paper.dropbox.com/doc/LUNCHBOX--AhRzMBXuVYEGt83_OvSLXdORAQ-Tc9yk629HImr1DXdMMb6L