[백준 1263번] 시간 관리 (C++)

문제 링크 : https://www.acmicpc.net/problem/1263

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, a, b;
vector<pii>v;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++) 
    {
        cin >> a >> b;
        v.push_back({b, a});
    }

    sort(v.begin(), v.end(), greater<>()); //일을 끝내야 하는 시간이 큰 값부터 정렬
    
    int cur = v[0].first - v[0].second; //현재 남은 시간
    for(int i=1; i<v.size(); i++)
    {
        cur = min(cur, v[i].first) - v[i].second;
    }
    
    cout << (cur < 0 ? -1 : cur);

    return 0;
}

 

일을 끝내야 하는 시간이 큰 값부터 순서대로 정렬을 해준다.

이후 초기값으로 (첫 번째 일을 끝내야 하는 시간 - 일을 처리하는데 필요한 시간)을 하여 남은 시간을 계산한다.

 

이후 해당 값을 토대로 현재 남은 시간에서 값을 계속하여 빼준다.

여기서 우리가 체크해야 할 것은 남은 시간보다 일을 끝내야 하는 시간이 더 긴 경우이다.

이 경우에 시간이 없는데도 일을 하는 경우가 생기게 된다.

 

따라서 남은 시간보다 일을 끝내야 하는 시간보다 더 긴 경우에는 다음 일이 끝나는 시간으로 갱신해줄 필요가 있고,

남은 시간이 일을 끝내야 하는 시간보다 짧은 경우에는 해당 일을 끝내야 하는 시간에서 필요 시간을 빼주면 된다.

결과적으로는 기존에 구한 남은 시간과 새로운 일을 끝내야 하는 시간 중에서 더 작은 값을 고르면 된다.

이렇게 구한 값이 0보다 작으면 불가능한 케이스이므로 -1을 출력하고, 아니라면 구한 값을 출력해준다.