백준 6068 시간 관리하기(C++)

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> arr;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i].second >> arr[i].first;
    }


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

    int s = arr[0].first - arr[0].second;
    int cur = arr[0].first;
    for (int i = 1; i < n; i++) {
        if (cur + arr[i].second > arr[i].first) {
            s -= cur + arr[i].second - arr[i].first;
            cur = arr[i].first - arr[i].second;
        }
        if (s < 0) {
            cout << -1;
            return 0;
        }
        cur += arr[i].second;
    }

    cout << s;



    return 0;
}

1. 문제

하루 해야 할 n개의 일의 요구 시간과 데드라인 시간이 주어진다. 하루는 0부터 시작하고, 본인은 최대한 늦게 일어나서 모든 일을 끝마치려고 할 때, 그 기상 시각을 출력하라. 단, 언제 일어나더라도 모든 일을 제 시각에 끝마칠 수 없다면 -1을 출력한다.

2. 풀이

최대한 늦게 일어나는 것이 목표이므로 그리디하게 접근할 수 있다. 그리고 일단 일어난 후 다음 일들은 제 시각에 모두 끝내는 것이 목표이므로 다음과 같이 해결한다.

    for (int i = 0; i < n; i++) {
        cin >> arr[i].second >> arr[i].first;
    }


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

우선 제 시각에 모두 일을 끝내야 하므로 일의 순서는 데드라인 순으로 정렬한다.

    int s = arr[0].first - arr[0].second;
    int cur = arr[0].first;

기상 시각(s)를 첫 일의 데드라인에 최대한 붙여서 잡는다. 그렇게 되면 데드라인에서 첫 일을 하는데 걸리는 시간을 뺀 시각이 기상 시각이 된다. 그리고 이후의 일을 스케쥴링하기 위해 현재 시각을 첫 일의 데드라인으로 잡는다.

    for (int i = 1; i < n; i++) {
        if (cur + arr[i].second > arr[i].first) {
            s -= cur + arr[i].second - arr[i].first;
            cur = arr[i].first - arr[i].second;
        }
        if (s < 0) {
            cout << -1;
            return 0;
        }
        cur += arr[i].second;
    }

이후 각 일에 대해 이전 일에 붙여서 수행하게 된다. 만약 현재 일을 수행할 때 데드라인을 넘어가는 경우 기상 시각부터 시작하여 모든 스케쥴을 초과한 시간만큼 당겨서 스케쥴링을 한다. 만약 그랬을 때 기상 시각이 음수가 될 경우 문제의 조건에 맞지 않게 되므로 모든 일을 수행할 수 없으므로 -1을 출력한다. 그 후 현재 일에 걸리는 시간만큼 cur에 더해준다.

 

모든 연산이 끝나고 기상시각을 출력하면 정답을 구할 수 있다.