[BOJ][C++] 백준 27112번: 시간 외 근무 멈춰!

https://www.acmicpc.net/problem/27112

27112번: 시간 외 근무 멈춰!

 

문제

오늘도 여러 체계의 개발 임무를 열심히 수행 중인 준민이에게 갑자기 새로운 개발 프로젝트가 들어왔다. 해당 개발 프로젝트는 총 N$N$개의 작업으로 이루어져 있으며, 각 작업은 ti$t_i$의 근무일이 필요하며 개발 프로젝트가 시작한 이후 di$d_i$일이 지나기 전에 끝내야 한다. 그러나 평시 근무만으로는 모든 N$N$개의 작업을 시간 내에 끝내기 힘들어 보였던 준민이는 개인 정비시간을 포기하며 시간 외 근무를 하고자 한다.

개발 프로젝트는 월요일부터 시작하며, 평시 근무는 월요일부터 금요일까지만 진행한다. 시간 외 근무는 요일과 관계없이 매일 최대 한 번씩만 진행할 수 있으며, 시간 외 근무를 1$1$회 진행하면 1$1$일치 업무를 끝마칠 수 있다.

준민이는 이를 토대로 효과적인 일정을 짜고 싶었지만, 이미 프로젝트로 너무 바빠진 준민이는 일정을 짤 시간조차 없는 상태이다. 바쁜 준민이를 위해, 모든 작업을 마감 기한 전까지 끝내고자 할 때 해야 하는 최소 시간 외 근무 일수를 알려주자.

입력

첫 번째 줄에 작업의 개수 N$N$이 주어진다. (1≤N≤100000)$(1\leq N\leq 100\,000)$ 

두 번째 줄부터 N+1$N+1$번째 줄까지, 각 작업의 마감 기한을 나타내는 정수 di$d_i$와 작업에 걸리는 시간을 나타내는 정수 ti$t_i$가 공백으로 구분되어 주어진다. (1≤di,ti≤100000)$(1\leq d_i,t_i\leq 100\,000)$ 

출력

모든 작업을 마감 기한 전까지 끝낼 수 있도록 하는 최소 시간 외 근무 일수를 출력한다.

만약 어떻게 해도 마감 기한 전까지 모든 작업을 끝낼 수 없다면, −1$-1$을 출력한다.

 

풀이

우선, 마감일이 빠르면서 걸리는 시간이 적은 순서로 업무들을 정렬한다.

날짜를 늘려가면서 매일 주어진 업무를 하루치씩 할 것이다.

단, 현재 업무의 마감일이 지났다면 해당 업무의 남은 일을 추가업무 시간에 배정한다.

이때, 추가업무시간이 현재 날짜를 넘어선다면 이 경우 하루에 한번씩만 추가업무를 할 수 있다는 조건이 위배되므로 -1 출력

 

그리디 문제이기 때문에 손으로 직접 배정해보고 시뮬레이션 해본 뒤 코드를 보면 이해가 쉬울 것이다.

 

만약 11%에서 막힌다면 범위를 확인하자 (100,000 * 100,000 > int범위)

만약 24%에서 막힌다면 마감시간이 같은 작업이 두개 이상 있는 경우를 생각하자.

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> ci;

bool cmp(ci a, ci b) {
    if(a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, a, b;
    cin >> n;
    vector<ci> v;
    for(int i=0; i<n; i++) {
        cin >> a >> b;
        v.push_back({a, b});
    }
    
    // 마감일이 앞선 순 -> 걸리는 시간이 적은 순 으로 정렬
    sort(v.begin(), v.end(), cmp);
    
    int idx=0; // idx : 현재 진행중인 작업 번호, v[idx]={마감 날, 필요한 시간}
    long long ans=0; // ans : 초과 근무 일 수
    for(long long day=0; idx<n; day++) {  // 매일 작업 하기
        
        // 현재 작업의 마감 기한이 넘어갔다면
        while(v[idx].first < day) {
            // 남은 작업 초과근무
            ans += v[idx].second;
            if(ans >= day) {  // 초과근무날이 오늘날짜보다 크다면 -1 출력 후 종료
                ans = -1;
                break;
            }
            // 다음 업무
            idx++;
            if(idx >= n)  // 업무 끝나면 종료
                break;
        }
        if(ans == -1)
            break;
        
        // 토요일, 일요일 휴식
        if(day%7==6 || day%7==0)
            continue;
        
        // 오늘의 작업
        v[idx].second--;  // 현재 작업의 남은 시간 - 1
        if(v[idx].second == 0)
            idx++;  // 작업 하나 끝냈으면 다음 작업 넘어가기
    }
    
    cout << ans;
    
    return 0;
}

/*
 */