[BOJ 9576] 책 나눠주기

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

9576번: 책 나눠주기

Tag : greedy

 

문제요약

각 학생은 [a, b]에 있는 책을 하나씩 고를 수 있다. 책 한권은 한 사람만 고를 수 있다.

이 때 최대 매칭을 구하라.

 

풀이

이 문제를 처음봤을 땐 티어를 안보고 생각해서 이건 무조건 이분매칭 기본 문제다! 라고 생각했던 기억이 있네요.

(http://boj.kr/2563bad26f364ee6aa5c04e9f97845b7 이분매칭 AC 코드)

 

정해로 돌아와서 생각해보면 기본적인 전략은 다음과 같다. 

1. 학생을 b 기준으로 정렬한다.

2. b가 작은 학생부터 훑으며 현재 고를 수 있는 가장 왼쪽의 것을 고른다. 

이 그리디가 왜 성립할까?

 

일단 a < b < c < d인 a, b, c, d에 대해 두 학생의 구간이 [a, c], [b, d]인 경우를 생각해보자. 

이런 경우에 구간 [b, c]에 책이 존재하며 구간 [a, c]는 아직 매칭되지 않았으며 이를 [b, d]에 매칭시키는 최적해가 존재한다고 가정하자. 

그렇다면 이를 [a, c]에 옮겨도 최적해는 같다. 

 

그러면 문제가 될법한 것중 남은 경우는 두 학생의 구간이 [a, d], [b, c]인 경우 하나 뿐이다.

lemma) [b, c]에 존재하는 책을 [a, d]에 매칭하는 최적해가 존재한다면 이를 [b, c]에 옮겨도 여전히 최적해이다.

 

proof)

구간 [a, d]에 책이 하나 더 존재한다면 [b, c]에 이미 매칭한 것을 옮겨주면 매칭의 개수가 증가하기 때문에 이는 최적해가 아닙니다.

구간 [a, d]에 책이 하나 더 존재하지 않는다면 이를 [b, c]에 옮겨도 최적해입니다. 

 

가능한 가장 왼쪽에 배치해야 하는 것은 회의실 배정의 원리이기 때문에 링크로 대체합니다.

https://kim1109123.tistory.com/34

[BOJ 8980] 택배

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int tc=1;
    cin >> tc;
    while(tc--){
    int n, m; cin >> n >> m;
    vector<pair<int, int>> v(m);
    for(auto &[r, l] : v) cin >> l >> r;
    sort(v.begin(), v.end());
    vector<int> chk(n + 1);
    int ans =0 ;
    for(auto &[r, l] : v) {
        int mn = 0;
        for(int i=l; i<=r; i++) if(chk[i] == 0) {
            mn = i;
            break;
        }
        if(mn){
            ans++;
            chk[mn] = 1;
        }
    }
    cout << ans << endl;
    }
}

---

https://kim1109123.tistory.com/17 

AtCoder Beginner Contest 214

이 문제에서는 구간의 길이가 1000이기 때문에 나이브하게 구해줘도 됩니다만 조금만 더 생각을 해봅시다.

만약 구간의 크기가 \(10^9\)까지라면? 그 때도 \(O(NM)\) 풀이를 짤 순 없잖아!

이같은 문제를 풀고 비슷한 생각을 해서 문제를 냈는지는 모르겠지만 구간의 크기가 \(10^9\)인 문제가 존재합니다.

위 글의 e번이 딱 그 문제입니다. 

 

저런 무지막지한 제한에서 아직 사용하지 않은 최소를 구하기는 어려워보입니다. 

제가 아는 선에서는 두 가지 풀이가 존재합니다.

 

1. 경로 압축

2. 세그먼트 트리

---

1. 경로 압축

경로 압축이 뭐냐? 하면 유니온 파인드에서 한번 루트까지 올라가면서

그 경로에 있는 정점들에 루트와 직접적인 간선을 만들어주는 그것이 경로압축의 예시입니다. 

 

find(i)를 i 이상인 것 중 매칭되지 않은 가장 왼쪽의 것 이라고 정의하겠습니다.

path[i] 배열에는 각각 다음 점으로 갈 경로를 연결해줍니다. 

아무것도 사용하지 않았을 때 find(i) = i 이며 find(L)을 호출해 얻은 것이 R이라면

R은 R + 1과 연결됩니다. ( path[R] = R + 1 ) 

path 배열을 어떻게 정의한다는 말이냐? 라고 할 수 있습니다. 

이는 unordered_map과 같은 자료구조를 사용해 실제 필요한 정점만 관리하면 됩니다.

경로압축만 적용했을 때 유니온 파인드의 시간복잡도는 \(O(logN)\)이기 때문에 

이 풀이의 시간복잡도는 \(O(MlogM)\)이 됩니다. 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
unordered_map<ll,ll>pa;
ll find(ll a){
    if(pa[a]==0)return a;
    else return pa[a]=find(pa[a]);
}
void merge(ll a, ll b){
    pa[find(b)]=pa[find(a)];
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc; cin >> tc;
    while(tc--){
        pa.clear();
        int N,M,cnt=0; cin >> N >> M;
        vector<pair<ll,ll>> v(M); for(auto &[i,j]: v) cin >> i >> j;
        sort(all(v), [&](pair<ll,ll>&a,pair<ll,ll>&b){ return a.se<b.se; });
        for(auto &[i,j]:v){
            ll q=find(i);
            if(q>j){}
            else cnt++,pa[q]=q+1;;
        }
        cout<<cnt<<endl;
    }
}

---

2. 세그먼트 트리

세그먼트 트리에서 사용되지 않은 정점 i의 초기값은 i로 두고 사용했다면

이를 적당히 큰 수로 바꿔줍니다. 

이렇게 관리를 잘 해주면 구간 [a, b]의 학생은 query(a, b)의 값에 매칭 후 이를 큰 수로 업데이트 해주면 됩니다.

(아래는 제한이 더 큰 문제에서 다이나믹 세그로 짠 코드에요)

 

전체코드

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc; cin >> tc;
    while(tc--){
        int N, M; cin >> N >> M;
        vector<pair<ll,ll>> v(M); for(auto &[i,j]: v) cin >> i >> j;
        sort(all(v),[&](pair<ll,ll>a,pair<ll,ll>b){ return a.se < b.se; });
        Node *root = new Node();
        int cnt = 0;
        for(auto &[i, j] : v){
            ll q = query(root,1,2e9,i,j);
            if(q > j or q > N) {
            } else cnt++;
            update(root,1,2e9,max(q,i),2e18);
        }
        cout << cnt << endl;
    }
}

---

3. 세그먼트 트리 + 이분탐색

아직 나눠주지 않은 책을 1로 채워두고 [a, b]구간에서 구간합이 1이 넘는 구간을 찾는 이분탐색을 돌리며 됩니다.

평가함수는 chk(mid) = sum(a, mid) < 1 과 같이 짤 수 있습니다.