백준 7983 - 내일 할거야

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

7983번: 내일 할거야

---

문제를 요약해봅시다.

• 과제 \(N\)개를 적절한 순서대로 배치하여 모든 과제를 늦지 않게 해결해야 합니다. 과제 \(i\)를 \(d_i, t_i\)라 할 때, 이 과제는 적어도 시간 \(t_i - d_i\)이 되기 전에 시작해야 합니다.
• 가장 먼저 시작하는 과제의 시작 시간을 최대화해야 합니다.
• 문제에는 자세히 적혀있지 않지만, 한 번에 동시에 최대 하나의 과제만 할 수 있습니다.

---

음.. 문제 설명을 읽으니 정말 공감이 마구 되네요.. ㅠ

 

우선 제일 간단하게 생각해봅시다. 모든 과제를 각각의 기한 \(t_i\) 내에 해결하려면 그냥 시간이 \(t_i - d_i\)일 때 과제 \(i\)를 시작하면 됩니다. 정말 간단하네요!

이 방법은 과제의 시작 시간과 제출 기한이 전혀 겹치지 않는다면 사용할 수 있습니다. 하지만 냉혹하게도 과제들은 여러 개가 연속으로 마구 나올 수 있고, 제출 기한도 겹칠 수 있습니다. 다른 방법을 생각해 봐야겠죠.

 

과제를 할 때 굉장히 중요한 것은 제출 기한입니다. 따라서 제출 기한에 초점을 두고 해보도록 합시다.

현재 이 문제는 모든 과제를 제출 기한에 늦지 않게 제출하되, 최대한 늦게 시작하는 날짜 구하기인데요, 이를 뒤집어 생각해 봅시다.

제출 기한을 과제를 받는 시간이라고 생각하는 겁니다! 시간의 흐름을 반대로 생각해서 제출 기한에 과제를 받고, 과제에 걸리는 시간만큼 지난 후 과제가 끝난다고 생각해봅시다.

이러면 이 문제를 모든 과제를 시작할 수 있을 때 바로 시작하고, 다 끝냈을 때 남는 시간 구하기로 바꿔 생각할 수 있습니다.

문제의 설명에서 '오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.' 라 했으므로 답은 항상 존재합니다.

 

문제를 바꿔 생각하면 이렇게 해결할 수 있습니다.

• 과제를 제출 기한이 느린 순서대로 정렬합니다.
• 시간 \(t_i\)이 제출 기한인 과제는 시간 \(t_i\)에 시작해서, 시간 \(t_i - d_i\)에 끝난다고 생각할 수 있습니다.
• 다음 과제의 제출 기한을 \(t_j\)라 할 때, \(t_j < t_i-d_i\)이면 다음 과제는 \(t_j\)에 시작하고, \(t_j \ge t_i+d_i\)이면 \(t_i+d_i\)에 시작합니다.
• 이를 모든 과제에 대해 반복한 후, 마지막 과제가 끝나는 시간을 기록합니다.

 

시간복잡도는 과제 \(N\)개의 정렬과 과제 \(N\)개를 순회하며 시간을 계산하는 두 단계가 있으므로 \(O(N \log N + N) = O(N \log N)\) 입니다.

 

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

// 과제 제출 기한의 역순으로 정렬하게 해주는 함수.
bool cmp_deadline(const pair<int, int> &p1, const pair<int, int> &p2) {
    return p1.second > p2.second;
}

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    // {과제 하는데 걸리는 시간, 과제 제출 기한}
    vector<pair<int, int>> hw(n);
    
    for (int i = 0; i < n; i++) {
        int d, t;
        cin >> d >> t;
        
        hw[i] = make_pair(d, t);
    }
    
    sort(hw.begin(), hw.end(), cmp_deadline);
    
    int start_time = hw[0].second;
    
    for (int i = 0; i < n; i++) {
        start_time = min(start_time, hw[i].second);
        start_time -= hw[i].first;
    }
    
    cout << start_time;
    
    return 0;
}