백준 6068

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다.

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입력

첫 줄에는 일의 개수인 N을 받고

두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다.

출력

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

풀이

처음엔 그냥 S_i의 총합에 T_i의 총합을 빼면 되는줄 아니었는데 틀렸다.

왜 틀렸나 생각해보니까 가장 늦게 일어나도 되는 시간에, 중간 중간 쉬는시간이 포함되어서 그랬던 것이다.

그러므로 가장 끝나는 시간이 늦은 경우부터 일을 끝내기 위해 필요한 시간을 빼주면서, 만약 S_i가 이전 노드의 S_i - T_i보다 작으면 S_i를 새로운 기준으로, 아니면 S_i - T_i를 새로운 기준으로 삼을 수 있게 했다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int S, T, N, ans=-1;
vector<pair<int,int>>v;
int main(){
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>T>>S;
        v.push_back({S, T});
    }
    sort(v.begin(),v.end(),greater<>());
    for(auto e : v){
        if(ans == -1){
            ans = e.first - e.second;
            continue;
        }
        if(e.first < ans)
            ans = e.first - e.second;
        else
            ans -= e.second;
    }
    
    if(ans < 0) cout<<-1;
    else cout<<ans;
    
}