[C++] 백준/BOJ - 6068 : 시간 관리하기

---

문제 이해 단계

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

6068번: 시간 관리하기

N개의 해야 할 일에 대한 정보가 들어온다.

해야 할 일에 대한 정보는 (하는 데 걸리는 시간, 끝내야 하는 시간)의 쌍으로 들어온다.

이러한 조건일 때, 제 시간 안에 끝낼 수 있는 한도 내에서
 존이 가장 늦게 일어나도 되는 시간을 구하는 문제

시간은 t = 0부터 시작된다.

 

---

문제 접근 단계

문제의 제한사항부터 보면 정보 N은 최대 1,000개까지 들어오고,
시간 T는 최대 1,000까지이다.

그리고 끝내야 하는 시간 S는 1,000,000까지이다. 

이 문제에서 끝내야 하는 시간 S는 정해져 있기 때문에 고정되어 있다.
그리고 흐르는 시간 T만 변하기 때문에 N * T = 10^3 * 10^3 = 10^6까지가 최대이다.

즉 int 자료형을 넘어가지 않아 오버플로우는 신경 쓰지 않아도 될 것 같다.

---

모든 작업이 가능한지 판단하는 법

입력으로 들어오는 두 정보는 (걸리는 시간, 끝내는 시간)이다.

여기서 무조건 끝내는 시간에
딱 맞추는 것이 아닌 끝내는 시간 안에만 마치면 된다.

즉, 최소한 (끝내는 시간 - 걸리는 시간)만 확보되면 해당 일을 할 수 있다는 것이다.

그럼 모든 일을 전부 다 실행하려면, 모든 일에 대해
(끝내는 시간 - 걸리는 시간) 이상의 여유 시간을 확보해 두는 것이 유리하다.

이를 유리하게 하려면, 끝나는 시간이 늦은 것을 뒤로 보낼수록 여유시간이 늘어난다.

예를 들어서 (3,10) 즉, 일하는데 '3'이 걸리고 '10'안에 끝내야 하는 일이 있다고 하자.
이 일을 끝내기 위해서는 적어도 '7' 안에는 시작해야 한다.

만약 (3,10)이 아니라 (3,20)이라면
쓸 수 있는 시간이 '17'로 늘어나 훨씬 여유로워진다.

그렇기 때문에 모든 일이 가능한지 판단하기 위한 최선의 방법은
끝나는 시간이 빠른 순으로 배치하는 것이다.

예제에 있는 그림으로 나타내면 이렇게 된다.

끝나는 시간이 빠른 순으로 배치하여 일하는 시간을 더한다.
더하다가, 현재 시간이 현재 끝나는 시간을 초과하면 가능하지 않다는 뜻이다.

---

최소 시간 구하기

그럼 우리가 답으로 구해야 하는 최소 시간은 어떻게 구해야 할까?
간단하다.

가장 많은 최소 시간을 요구하는 일을 찾아 그 시간을 시작으로,
1씩 줄여나가면서 가능한 게 있는지 판단하면 된다.

예제 입력 1을 예시로 들면,
가장 많은 최소시간을 요구하는 (5,20) or (1,16)을 보자.

이 2개는 최소한 15시간 전에는 시작해야 한다.

그래서 15를 기준으로 시작하여 안되면
14, 그다음 13..12...11.. 이런 식으로 줄여나간다.

줄여나가다 0 미만이 되면 안 되는 것이므로 끝낸다.

자세한 것은 문제 구현 단계에서 살펴보도록 하자.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// (필요한 시간, 끝내는 시간)을 담은 구조체
struct Work{
    int need;
    int end;
};

// 끝내는 시간으로 정렬
bool compare(Work a, Work b){
    if(a.end == b.end) return a.need < b.need;
    return a.end < b.end;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<Work> v(N); // 일을 담을 벡터
    int avail = 0;
    for(int i = 0; i < N; i++){
        int v1, v2;
        cin >> v1 >> v2;
        v[i] = {v1,v2};
        avail = max(avail,v2-v1); // 필요하는 최소 시간이 가장 많은 걸 시작 시간으로 둚
    }
    sort(v.begin(),v.end(),compare); // 정렬

    // 0 이상일때까진 반복
    while(avail >= 0){
        int cnt = avail; // cnt -> 현재 시간
        int success = true; // 성공했는가 실패했는가
        for(int i = 0; i < v.size(); i++){
            cnt += v[i].need; // 그 일에 걸리는 시간을 더해줌
            if(cnt > v[i].end){ // 끝내는 시간을 넘었을 때
                avail--; // 1 감소시켜주고 success = false;
                success = false;
                break;
            }
        }
        if(success) break; // 성공 시 더이상 할 필요 없음
    }
    cout << avail;
}

위에서 설명한 것을 구현한 코드이다.

이 문제는 정렬과 그리디를 이용한 문제이므로 코드는 그렇게 복잡하지 않다.

Work라는 구조체를 선언해 줌으로써 좀 더 보기 편하게 만들어줬다.
그리고 끝내는 시간을 기준으로 정렬해 주기 위해 정렬기준 compare을 세웠다.

avail을 위에서 말했던 최소 시간 요구량이 가장 많은 것으로 초기화했다.

핵심적인 것은 while문인데,
cnt라는 현재 시간에 그 일에 대한 필요한 시간을 계속 더해주면서
해당 일에 끝나는 시간을 넘었는지 체크한다.

만약 넘었다면 avail을 1씩 깎아가며 반복한다.

만약 성공했다면, 우리가 구해야 하는 것은
최댓값이므로 더 이상 할 필요가 없으므로 탈출하고 끝낸다.

 

---

시행착오

그리디 문제인 것은 바로 알고, 정렬 기준도 바로 알았다.
헤맸던 부분은 가장 첫 값을 뭐로 잡아줘야 하는 부분.

저거 때문에 30분을 날린 것 같다.

나중에는 아예 로직이 틀린 줄 알고 로직도 바꿔봤는데
그냥 저거 처리 잘못해 줘서 그랬다.

나는 그냥 정렬해 주고 가장 처음 값에 대해서만 해주면 될 줄 알았는데 그게 아니었다.
너무 쉽게 생각했나 보다.

 

생활비..

https://toss.me/howudong

howudong님에게 보내주세요