[종만북] LUNCHBOX - Microwaving Lunch Boxes (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-LUNCHBOX

 

 

풀이

  N개의 Lunch Box가 있고, 각각 전자렌지에 돌리는 시간 M과 먹는시간 E를 가지는 상황이다.

여기서 고정인 부분은 전자렌지 돌리는 시간 M는 무조건 N개의 M을 전부 더한 시간만큼이 필요하다. 반면에 먹는시간 E는 각 M이 끝날때마다 시작된다. 예를들어 아래와 같은 입력을 보자.

1
3
1 3 2
10 4 1

 

  순서대로 진행해본다면 아래와 같이 진행된다.

 

  사실 저 순서대로 처리하는게 풀이인데, 결국 M의 총합은 항상 고정이고, E가 시작하는건 각 M이 끝난 이후이므로 E가 긴 녀석을 최대한 빨리 먹기 시작해서 처리하는게 무조건 이득이다. 따라서 E값 내림차순으로 정렬한 후 (E가 동일할 시 M을 내림차순으로할지 오름차순으로 할지는 상관없다.), 현재까지의 M값의 합 + 현재 E값의 최대치를 찾으면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine().trim());
        while (t-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        LunchBox[] lunchBoxes = initLunchBox(n);
        Arrays.sort(lunchBoxes);

        int answer = 0;
        int mSum = 0;
        for (int i = 0; i < n; i++) {
            mSum += lunchBoxes[i].m;
            answer = Math.max(answer, mSum + lunchBoxes[i].e);
        }

        sb.append(answer).append('\n');
    }

    private LunchBox[] initLunchBox(final int n) throws Exception {
        LunchBox[] lunchBoxes = new LunchBox[n];
        for (int i = 0; i < n; i++) {
            lunchBoxes[i] = new LunchBox();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            lunchBoxes[i].m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            lunchBoxes[i].e = Integer.parseInt(st.nextToken());

        return lunchBoxes;
    }
}

class LunchBox implements Comparable<LunchBox> {
    int m, e;

    @Override
    public int compareTo(final LunchBox o) {
        if (this.e == o.e) {
            return this.m - o.m;
        }
        return o.e - this.e;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.