[BOJ] 시간 관리하기 6068번 C++

 

 

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 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 을 출력하라.

 

접근 방식

 

다음과 같은 방식으로 풀 수 있다.

1. 마감 기한 기준으로 정렬하기

2. 가장 늦은 시간부터 작업하기

2-1. 이때, 마감 기한이 현재 시간보다 크거나 같으면 현재 시간에서 작업 시간을 뺀다.

2-2. 마감 기한이 현재 시간보다 작으면 마감 기한에서 작업 시간을 뺀다.

3. 현재 시간을 확인해서 0 미만이면 모든 작업을 하루 안에 처리하지 못한것 이므로 -1을 출력하고, 아니면 현재 시간을 출력한다.

 

즉, 예제

3 5
8 14
5 20
1 16

 를 받았을 때,

 

먼저

20 5
16 1
14 8
5 3

으로 정렬해주고

 

현재 시간을 가장 큰 값인 20으로 잡아서 시작해준다.

20 -> 15 -> 14 -> 6 -> 2로 출력값은 2가된다.

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    vector<pair<int,int>> v(N);

    for(int i=0; i<N; i++) cin>>v[i].second>>v[i].first;

    sort(v.begin(),v.end(), greater<>());
    int min = v[0].first;

    for(auto c : v) {
        if(min <= c.first) min -= c.second;
        else min = c.first - c.second;
    }

    if(min < 0) cout<<-1;
    else cout<<min;
}