[BOJ] 1263번 - 시간 관리

백준 1263번 - 시간 관리

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	419	206	175	55.031%

문제

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

입력

첫째 줄에 일의 수 N이 입력되고 다음 N(1≤N≤1,000)개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti(1≤Ti≤1,000)와 Si(1≤Si≤1,000,000)가 입력된다.

출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

---

예제 입력 1

4
3 5
8 14
5 20
1 16

예제 출력 1

2

출처

www.acmicpc.net/problem/1263

1263번: 시간 관리

알고리즘 분류

• 그리디 알고리즘

접근 방법

해당 문제를 "K시간에 최초의 일을 시작했을 때, 모든 작업을 수행할 수 있는가?" 라는 결정문제로 치환하여 생각해보자.

그러면 특정 ${K_n}$값을 기준으로 참/거짓으로 이분화 되게 된다.( 이것을 명제 P라고 가정하자 )

k시간에 최초의 일을 시작했을 때 모든 일을 다 끝낼 수 있다면, k-1시간에도 모든 일을 다 끝낼 수 있다는 것이 자명하기 때문이다.

이 사실을 통해서 Parametric Search를 수행하게 된다면 ${P(k) 가 true인 최대의 k}$값을 구할 수 있게 되고, 이것이 우리가 원하는 최적해가 된다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int,int>> info;
int answer = -1;
bool canDo(int start){
    // start에서 시작해서 모든 일을 마칠 수 있는가?
    int time = start;
    for(int i=0; i<info.size(); i++){
        if( time + info[i].second > info[i].first ){
            return false;
        }
        time += info[i].second;
    }
    return true;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N;

    info.resize(N);
    for(int i=0; i<N; i++){
        cin >> info[i].second >> info[i].first; // 마감시간, 소요시간
    }
    sort(info.begin(), info.end());

    long long left = 0, right = 1000 * 1000000;
    while(left <= right ){
        long long st = (left+right)/2; // 시작 시간
        if( canDo(st) ){
            answer = st;
            left = st + 1;
        }else{
            right = st - 1;
        }
    }
    cout << answer;


    return 0;
}