[알고리즘 풀이 분석] BOJ 6068 시간 관리하기

오늘 풀어본 문제는 BOJ 6068 시간 관리하기 이다! 알고리즘 분류에 관계 없이 매일 4문제씩 뽑아주는 오늘의 문제 에서 골라 풀었고 골드 5단계 문제였다!

BOJ 6068 시간 관리하기

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다.

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입출력

나의 풀이

주어지는 일들 마다 모두 데드라인 시간이 주어지므로 데드라인이 가장 늦은 일부터 채워나가야 한다고 생각했다. 말하자면 그리디 알고리즘 인 것 같다.

<algorithm> 헤더의 sort 함수를 이용해 주어진 일들이 담긴 배열 task 를 데드라인이 늦은 순서대로 정렬 하고 int 형 변수 limit 의 값을 task[0].second 로 초기화 해 limit 값을 줄여 나간다.

limit 이 해당 task의 데드라인 보다 이후이면 limit을 해당 데드라인으로 땡겨준 뒤 task를 수행하는데 필요한 시간만큼 limit을 줄인다.

모든 task를 탐색한뒤 limit은 게으른 존이 limit 시간에만 일어나면 모든 일을 시간 안에 마칠 수 있다는 뜻이고, limit 값이 0보다 작다면 주어진 시간 안에 모든 task 를 해낼 수 없다는 뜻이므로 -1 을 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 데드라인 순으로 내림차순 정렬 
bool byDeadLine(pair<int, int> a, pair<int, int> b){
    if (a.second == b.second){
        return a.first>b.first;
    }else{
        return a.second > b.second;
    }
}

int getLatestTime(int N, vector<pair<int, int>> task){
    sort(task.begin(), task.end(), byDeadLine);

    int limit = task[0].second;
    for (int i = 0; i < N; ++i) {
        if (limit > task[i].second){  // limit을 데드라인으로 땡겨옴 
            limit = task[i].second;
        }
        limit -= task[i].first;  // 업무 수행 시간 만큼 줄임 
    }

    return limit;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    int need=-1, deadline=-1;
    vector<pair<int, int>> task;
    for (int i = 0; i < N; ++i) {
        cin>>need>>deadline;
        task.push_back(make_pair(need, deadline));
    }

    int wakeup = getLatestTime(N, task);
    if (wakeup < 0) wakeup = -1;

    cout<<wakeup;

    return 0;
}