(C++) - 백준(BOJ) 6068번 : 시간 관리하기

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

6068번: 시간 관리하기

그리디 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

필요시간, 끝나는 시간을 저장할 Work 구조체를 선언합니다. n, 정답 출력용 ans, Work구조체를 담을 vector v를 선언합니다.  1. n만큼 입력 후 v에 저장합니다. 2. 끝나는 시간이 오름차순이 되도록 저장합니다.

 

📔 풀이과정

 1. 일을 시작해야하는 마지노선 시간을 구해야하므로 끝에서부터 일하는 시간만큼 뺴면서 확인합니다.

 

 2 ans는 무한대에서 시작해 v[i]의 끝나는시간과 비교 후 최솟값을 저장합니다. i번째 일이 끝나는 마지노선이 곧 최솟값이 됩니다. 이 최솟값에서 i번째 일의 소요시간을 뺀다면 i번째 일의 시작 시간이 구해집니다. 끝나는 시간이 겹치더라도  농부가 동시에 일을 할 수 없기 때문에 가장 덜 소요되는 시간을 뺴주면서 반복하면 됩니다.

 

 3. 2를 i = 0까지 반복 수행합니다.

 

📔 정답출력

ans가 음수라면 일을 전부할 수 없는 상태이므로 -1을 출력합니다. 아니라면 ans를 출력합니다. 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
struct Work {int timeNeed, endTime; };
int n, ans=0x3f3f3f3f;
vector <Work> v;
bool cmp(Work &a, Work &b){
    if(a.endTime == b.endTime) return a.timeNeed < b.timeNeed;
    return a.endTime < b.endTime;
}
int main(){
    cin >> n;
    for(int i = 0,t,e; i < n; i++){
        cin >> t >> e;
        v.push_back({t,e});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i = n-1; i >= 0; i--){
        ans = min(ans, v[i].endTime);
        ans -= v[i].timeNeed;
    }
    if(ans < 0) cout << -1;
    else cout << ans;
}