[백준] 6068번 : 시간 관리하기 (C++)

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 을 출력하라.

 

 

 

 

 

 

 

풀이)

 

// 6068. 시간 관리하기
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<pair<int, int>> vec;
 
// 현재 시간에 필요한 시간을 더해가며
// 제 시간에 끝낼 수 있는지 확인한다.
bool check(int x)
{
    for (int i = 0; i < n; i++)
    {
        x += vec[i].first;
        if (x > vec[i].second)
        {
            return false;
        }
    }
 
    // x시간에 일어나도 다 마칠 수 있음.
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        vec.push_back(make_pair(a, b));
    }
 
    // 빨리 끝내야 하는 순으로 정렬한다.
    // ( 끝내야하는 순 정렬 )
    sort(vec.begin(), vec.end()
        , [](pair<int, int> a, pair<int, int> b)
            {return a.second < b.second; });
 
    // parametric search
    int s = 0;
    int e = 3000000;
 
    // 기본으로 ans는 -1로 설정한다.
    // 만약 존이 제시간에 일을 끝낼 수 없다면
    // -1을 출력해야 하므로
    int ans = -1;
    while (s <= e)
    {
        int mid = (s + e) / 2;
        // 만약 제 시간에 끝낼 수 있다면
        // 일어나는 시간을 늦춘다.
        if (check(mid))
        {
            s = mid + 1;
            ans = mid;
        }
        // 좀 더 일찍 일어난다.
        else
        {
            e = mid - 1;
        }
    }
 
    cout << ans;
 
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/