[BOJ 28964] Библиотека

백준 문제 링크

🔍 문제 분석

• 문제에서는 책을 빌린 날짜 s, 책의 반납기한 e, 책을 읽는 데 걸리는 시간 f가 주어진다. 따라서, 책을 반납해야 하는 기간은 [s + f, e]이다. 책은 하루에 한 권만 반납할 수 있으므로 구간 내에 적절한 지점에서 책을 반납해서 겹치는 지점이 없도록 해야한다.
• 구간이 여러개 주어지므로 라인 스위핑 알고리즘을 통해서 해결할 수 있다. 먼저 구간의 시작 지점을 기준으로 오름차 순으로 정렬하며, 시작 지점이 같을 경우 끝 지점을 기준으로 오름차 순으로 정렬한다.
• 변수 l과 r을 유지하면서 정렬된 전체 구간을 순회한다. 이 때, l은 마지막으로 책이 반납된 시점을, r은 현재까지 확인한 구간 중 가장 큰 오른쪽 값을 의미한다.

• 위 그림에서 i = 3인 경우 구간 [3, 3]에서 책을 반납해야 한다. 하지만, i = 2에서 이미 해당 구간이 사용되었다. 따라서, l > e이므로 책을 반납할 수 없다. 이러한 경우는 r을 통해서 해결할 수 있다. r이 l보다 크다는 것은 확인된 구간 중 l 시점에 책을 반납할 수 있는 경우가 존재함을 의미한다. 따라서, 두 구간의 반납 시점을 교환함으로써 두 책 모두 반납할 수 있게 된다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

int main() {
    fastio;

    int n;
    cin >> n;
    vpi v;
    for (int i = 0; i < n; ++i) {
        int s, f, c;
        cin >> s >> f >> c;
        v.emplace_back(s + c, f);
    }
    sort(v.begin(), v.end());
    int l = 0, r = 0;
    bool is_possible = true;
    for (auto [b, e] : v) {
        if (b > e) {
            is_possible = false;
            break;
        }
        l = max(l + 1, b);
        r = max(r, e);
        if (l > r) {
            is_possible = false;
            break;
        }
    }
    cout << (is_possible ? "YES" : "NO");
}

📝 코드 설명

🔧 트러블 슈팅

• 입력 데이터 중 책을 읽는 데 걸리는 시간이 길어 처음부터 반납할 수 없는 경우가 존재한다(b > e). 이 경우를 확인해 준다.

📚 참고자료