https://algospot.com/judge/problem/read/LUNCHBOX
algospot.com :: LUNCHBOX
Microwaving Lunch Boxes 문제 정보 문제 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 lun
algospot.com
코드설명
그리디(탐욕법, Greedy) + 병렬처리(Parallel Processing)를 활용합니다.
그리디 방식은, 각 도시락의 식사 시간이 최대한 늦은 것을 순서대로 먹어야 합니다.
문제에서 중요한점은, 먹는 과정은 전자레인지를 돌리는 과정과 다른사람이 밥먹는 과정이 동시에 일어날 수 있습니다. 즉, 병렬로 처리가능합니다. 아래와 같이 ret = Math.maxret, beginEat + E[box]) 로 해당 로직을 처리할 수 있습니다.
여러 사람이 동시에 도시락을 먹는 상황을 시뮬레이션합니다.
// 해당 순서대로 데워먹는 과정을 시뮬레이션한다.
int ret = 0, beginEat = 0;
for (int i = 0; i < N; i++) {
int box = order.get(i).foodIndex;
beginEat += M[box];
ret = Math.max(ret, beginEat + E[box]);
}
코드
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
private static int N, K, M;
private static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int C = Integer.parseInt(st.nextToken());
while(C-- > 0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[] M = new int[N]; // 각 도시락의 전자레인지 시간
int[] E = new int[N]; // 각 도시락의 식사 시간
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
M[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
E[i] = Integer.parseInt(st.nextToken());
}
System.out.println(heat(M, E));
}
}
private static int heat(int[] M, int[] E) {
// 어느 순서로 데워야 할지를 정한다.
ArrayList<Node> order = new ArrayList<>();
for (int i = 0; i < N; i++) {
order.add(new Node(-E[i], i));
}
Collections.sort(order);
// 해당 순서대로 데워먹는 과정을 시뮬레이션한다.
int ret = 0, beginEat = 0;
for (int i = 0; i < N; i++) {
int box = order.get(i).foodIndex;
beginEat += M[box];
ret = Math.max(ret, beginEat + E[box]);
}
return ret;
}
private static class Node implements Comparable<Node>{
int eatTime, foodIndex;
public Node(int eatTime, int foodIndex) {
this.eatTime = eatTime;
this.foodIndex = foodIndex;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.eatTime, other.eatTime);
}
}
}