boj 1263 시간 관리

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

 

문제를 보자마자 6068번 시간 관리하기 문제랑 같다는 것을 느꼈습니다.

마감 시간(Si)과 일을 하는데 걸리는 시간(Ti)이 주어지고, 언제부터 시작하면 일을 끝낼 수 있는지 구해야 합니다.

마감 시간 기준 내림차순으로 정렬하여 뒤에서부터 탐색한다면 쉽게 해결할 수 있습니다.

저는 혹시 몰라서 Si가 같다면 Ti 기준으로도 정렬을 했지만 생각해보니 그럴 필요는 없어보입니다.

 

시간을 최대로 세팅을 먼저 하고, 내려가면서 Ti를 빼주시면 되겠습니다.

도중에 현재 작업의 Si보다 t가 더 크다면 Si로 현재 시간을 조정해주시면서 진행해주시면 됩니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int t = 1e9;
    for (int i = 0; i < N; i++) {
        t = min(t, list[i].second);
        t -= list[i].first;
 
        if (t < 0) {
            cout << "-1\n";
            return;
        }
    }
 
    cout << t << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}