[BOJ] 1263 - 시간관리

Sierra·2022년 9월 20일

boj greedy 공부노트 대학생 알고리즘 코딩공부

[BOJ] Greedy

목록 보기

29/33

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

문제

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

입력

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

제한

1 ≤ N ≤ 1,000
1 ≤ Ti ≤ 1,000
1 ≤ Si ≤ 1,000,000

예제 입출력

예제 입력 1

예제 출력 1

Solution

#include <bits/stdc++.h>

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    return a.second > b.second;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    vector<pair<int, int>> vec(N+1);
    for(int i = 1; i <= N; i++){
        cin >> vec[i].first >> vec[i].second;
    }
    sort(vec.begin(), vec.end(), compare);
    
    for(int i = 0; i < N; i++){
        int minimumStartTime = vec[i].second - vec[i].first;
        if(minimumStartTime < vec[i+1].second){
            vec[i+1].second = minimumStartTime;
        }
    }
    vec[N].second = vec[N-1].second - vec[N-1].first;
    if(vec[N].second < 0) {
        cout << "-1\n";
    } else {
        cout << vec[N].second <<'\n';
    }
}

핵심은 정렬이다.

우선 입력받는 형태는 다음과 같다.

작업 소요 시간, 종료 한계 시간 (편의상 납기라고 하겠다.) 을 차례대로 입력받는다.
우리가 이 데이터를 통해 알아 내야 하는 것은 최종적으로 언제부터 일을 시작해야 납기 기간을 맞출 수 있느냐는 것이다.
납기 기간을 기준으로 정렬 해 보자. 그러면 데이터는 다음과 같을 것이다.

5시간이 걸리는 일을 20시 까지 끝내려면 언제 일을 시작해야 할까? 답은 간단하다. 15시다.
문제는 그 전 순서의 일의 납기 시간이 16시라는 것이다.
하지만 일을 하는 데 걸리는 시간은 1시간이다. 즉 16시보다 일찍 마칠 수 있다.
5시간 걸리는 일을 15시에 시작해야하니 1시간 걸리는 일의 납기 시간을 15시로 조정 해 줄 수 있다.