[백준][Java] 30088 - 공포의 면담

1. 문제 정보

https://www.acmicpc.net/problem/30088

30088번: 공포의 면담실

난이도 : S5

유형 : 정렬, 누적합, 그리디

시간 : O(NM + NMlongNM) (NM <= 1_000_000)

---

2. 풀이

부서 1개씩, 각 부서 내 모든 인원의 면담을 먼저 끝내야 시간이 적게 든다.

그러므로 각 부서의 총 면담 소요 시간을 기준으로 오름차순 정렬을 해준 뒤 시간을 누적해 주면 된다.

 

총 시간 = (부서1) + (부서1 + 부서2) + (부서1 +부서2 + 부서3) ...

---

3. 코드

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

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    int N;
    int M;
    int[] sum;
    long res;

    private void solution() throws IOException {

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

        Arrays.sort(sum);
        long prefixSum = 0;
        res = 0;
        for (int i = 0; i < N; i++) {
            prefixSum += sum[i];
            res += prefixSum;
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}