[Silver V] 공포의 면담실 - 30088

[문제 위치]

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

[문제 풀이]

이 문제는 그리디(정렬+누적합) 를 통해 해결하는 문제이다.
부서 i의 직원 면담 시간 합을 t_i라 두면 한 부서의 퇴근 시각은 그 부서를 끝낼 때의 누적 시간이 되고 전체 합은 처리 순서에 따른 누적합들의 합이므로 누적합의 합을 최소화하려면 t_i가 작은 부서부터 처리하면 되므로 부서별 합을 구해 오름차순 정렬한 뒤 누적합을 더해 답을 구하게 해결한다
아래는 이를 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO;
    int N;
    if (!(cin >> N)) return 0;

    vector<long long> sumDept(N);
    for (int i = 0; i < N; ++i) {
        int m; cin >> m;
        long long s = 0;
        for (int j = 0; j < m; ++j) {
            int t; cin >> t;
            s += t;
        }
        sumDept[i] = s;
    }

    sort(sumDept.begin(), sumDept.end());

    long long ans = 0, pref = 0;
    for (long long x : sumDept) {
        pref += x;      // 현재까지 누적 시간
        ans += pref;    // 이 시점에 끝난 부서의 퇴근 시각 합에 더함
    }

    cout << ans << '\n';
    return 0;
}