BOJ 28068 I Am Knowledge

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/28068

🧐 관찰 및 접근

#

• 지금 어떤 책을 읽을 수 있고, $a_k <= b_k$라면, 읽지 않을 이유가 없다.
• 나머지 $a_k > b_k$들인 책들은 어차피 읽을수록 즐거움이 감소만 하므로, $a_k$가 큰거부터 차례대로 읽으면 되지 않을까? 어떻게 그리디하게 가야하지?
  • 두 책 $i, j$가 있다고 해보자.
  • 이때, 두 책을 $i \rightarrow j$로 읽기 위해선
    • $F \geq a_i$
    • $F - a_i + b_i \geq a_j \rightarrow F \geq a_i + a_j - b_i$
    • 따라서 $F \geq \max(a_i, a_i + a_j - b_i) = \text{Cost}_{i \rightarrow j}$
  • 같은 방식으로, $j \rightarrow i$로 읽기 위해선
    • $F \geq \max(a_j, a_i + a_j - b_j) = \text{Cost}_{j \rightarrow i}$
  • 이 때, $b_i \geq b_j$라고 가정하자.
    • $a_i < a_i + (a_j - b_j)$
    • $a_i + a_j - b_i \leq a_i + a_j - b_j$
    • 이 두 식이 성립하므로, 언제나 $\text{Cost}_{i \rightarrow j} \leq \text{Cost}_{j \rightarrow i}$
    • 따라서 $b$의 내림차순으로 정렬 후 그리디가 성립한다.

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    vector<pii> v1, v2;
    rep(i, 0, N){
        int a, b; cin >> a >> b;
        if(a <= b) v1.push_back({a, b});
        else v2.push_back({a, b});
    }
    sort(all(v1));
    sort(all(v2), [](pii &p1, pii &p2){
        return p1.second > p2.second;
    });
    ll cur = 0;
    for(auto &p: v1){
        if(cur < p.first){
            cout << 0;
            return;
        }
        cur -= p.first;
        cur += p.second;
    }
    for(auto &p: v2){
        if(cur < p.first){
            cout << 0;
            return;
        }
        cur -= p.first;
        cur += p.second;
    }
    cout << 1;
}