[BOJ] 7983번 : 내일 할거야(C++)

문제 링크 : 백준 7983번

[문제 접근]

내일부터 연속으로 쉴 수 있는 최대값을 구하는 것이기 때문에 가장 빠른 제출일에서 얼마나 더 빨리 시작해야하는가를 구하면 된다.

제출일 - 과제하는데 걸리는 일 = 제출일에 과제를 끝내기 위해 과제를 시작해야하는 날(즉, 최대한 쉬다가 과제를 하는 경우).
= now라고 가정

1. 제출일을 기준으로 내림차순으로 정렬해준다.
2. 첫 now를 설정해준다.
3. now보다 다음 과제의 제출일이 작거나 같으면 해당 과제는 다음 과제에 영향을 미치지 않으므로 now를 처음과 같이 갱신해준다.
4. now보다 다음 과제의 제출일이 크면 다음 과제에 영향을 미치는 과제이므로 now에서 과제하는데 걸리는 일 만큼을 빼서 now에 갱신해준다.

[소스 코드]

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

using namespace std;
int n;
vector<pair<int, int>> arr;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        int a, b;
        cin >> a >> b;
        arr.push_back({a, b});
    }

    sort(arr.begin(), arr.end(), cmp);
    int now=arr[0].second-arr[0].first;
    for(int i=1 ; i<n ; i++) {
        int d=arr[i].first, t=arr[i].second;
        if(now>=t) {
            now = t-d;
        } else {
            now = now-d;
        }
    }
    cout << now;
    
    return 0;
}