7663번 Dreadful Deadlines

문제

---

7663번 Dreadful Deadlines - 백준

번역

---

데이빗은 과제를 n개 해야한다.
한 번 시작한 과제는 끝까지 달려야하고 한 번에 하나만 처리할 수 있다.
이때 데이빗이 데드라인 안에 과제를 끝낼 수 있는 가장 늦은 시간은 언제인가?

설계

---

또 다시 난이도를 알 수 없는 문제인데 번역해보니 그렇게 어려울 것 같진 않다?
우리에겐 그리디 알고리즘이 있으니까!
그리디… 그리디만 있다면…

구현

---

여러 케이스 들어오니 while문에 집어넣고
x와 t가 따로 들어오는걸 모아서 튜플로 만들어준다.

while(true){
    int n;
    cin >> n;

    if (n == 0) break;

    vector<int> x(n);
    vector<int> t(n);
    vector<tuple<int, int>> assignments;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i];
    }

    for (int i = 0 ; i < n ; i++) {
        cin >> t[i];
    }

    // 튜플로 만들어 넣기
    for (int i = 0; i < n; ++i) {
        assignments.push_back(make_tuple(x[i], t[i]));
    }
}

놀다가 제일 늦게 하고싶기 때문에 마감시간이 제일 늦은 순서로 정렬 후 탐색한다.
시간이 모자라면 불가능 처리

// 늦게 시작하고 싶으니 마감시간이 제일 늦은 과제부터 거꾸로 확인
sort(assignments.begin(), assignments.end(), compare);

int time = INT_MAX; 

// 과제 하나씩 체크
for (const auto& assignment : assignments) {
    int xi = get<0>(assignment);
    int ti = get<1>(assignment);

    time = min(time, ti);
    time -= xi;
}

// 시간이 부족하면 impossible
if (time < 0) cout << "impossible\n";
else cout << time << '\n';

// ... 중략 ...

// 커스텀 정렬 함수
bool compare(const tuple<int, int>& a, const tuple<int, int>& b) {
    return get<1>(a) > get<1>(b); 
}

채점

---

반성

---

이번엔 climits 헤더 빼먹어서 컴파일 에러 발생
정신을 못차리니 오늘은 쉬어야지

java문제 풀고 c문제 푸니 느끼는데 진짜 입출력이 사기다.
java였으면 테스트 케이스 사이 공백도 따로 처리해줬을텐데

코드 확인

---

Link to GitHub