책 나눠주기

코드

[ 이분매칭 풀이 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
vector<pair<int,int>> v(1010);
int work[1010];
bool finish[1010];
int T, N, M;
/* 이분 탐색 */
bool DFS(int x){
    for(int t=v[x].first;t<=v[x].second;t++)
    {
        if(finish[t]) continue;
        finish[t] = true;
        if(work[t] == -1 || DFS(work[t])){
            work[t] = x;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--)
    {
        v.clear();
        cin >> N >> M;
        for(int i=0;i<M;i++)
        {
            int a, b;
            cin >> a >> b;
            v.push_back({a,b});
        }
        /* 연결된 점의 좌표 초기화 */
        fill(work, work+1010, -1);
        int ans=0;
        /* 모든 점들에 대해 연결 */
        for(int i=0;i<M;i++)
        {
            /* 정점 방문 여부 초기화 */
            fill(finish, finish+1010, false);
            if(DFS(i)) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

• 로직
  • 모든 사람에 대해서 이분매칭 DFS 수행
    : 내가 선택한 책이 이미 선택되어 있다면
      그 책을 선택한 사람에게 다른 책을 선택하도록 권유!

• 핵심
  : 이분매칭 알고리즘의 이해

---

[ 그리디 풀이 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
bool compare(pair<int,int> n, pair<int,int> c)
{
    if(n.second == c.second)
        return n.first < c.first; // st가 작은수로 오름차순
    return n.second < c.second; // en이 작은수로 오름차순
}
int T, N, M;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> N >> M;
        vector<pair<int,int>> v;
        bool vis[N+1];
        fill(vis, vis+N+1, false);
        for(int i=0;i<M;i++)
        {
            int a, b;
            cin >> a >> b;
            v.push_back({a,b}); // st, en
        }
        // 그리디 조건
        // 1) en이 작은 순서대로 정렬
        // 2) en이 같다면 st가 작은 순서대로 정렬
        sort(v.begin(), v.end(), compare);
        int ans=0;
        for(int i=0;i<v.size();i++)
        {
            for(int j=v[i].first; j<= v[i].second;j++)
            {
                if(vis[j]) continue;
                vis[j] = true;
                ans++;
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

• 로직
  • 책의 범위를 (st, en) 라고 했을 때
    en이 작은 순서대로 정렬, en이 같다면 st이 작은 순서대로 정렬
  • 정렬된 순서의 사람순서대로 책 할당!

• 이해
  • 이 문제를 greedy하게 접근하기 위한 명확한 증거를 찾지 못함
  • 이분매칭의 경우에 그리디로 풀어낼 수 있다는 것 정도 인지하자

---