책 나눠주기 9576

문제

접근 방법

처음에 생각했을 때 낮은 순으로 정렬하여 bool 배열을 체크해가면 된다고 생각했다. 그렇게 하면 a가 낮은 순대로 채워나가며 책을 줄 수 있는 최대 학생 수가 나올 것 같았다. 하지만 바로 틀렸는데 이러한 경우가 있기 때문이다.

1, 7 1, 7 1, 7 2, 2

질문 게시판에서 찾아보고 알았다.
가장 낮은 수인 1로 인해 범위가 충분했는데도 2가 무시당한 것이다.
원래대로라면 다른 것을 기준으로 삼고 다시 풀어야 할 것 같았지만 굴복하고 싶진 않았다. 비효율적인 느낌이 들지만 수정하여 제출했다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int, int> book;
bool isVisted[1001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        priority_queue<book, vector<book>, greater<book>> pq;
        memset(isVisted, false, sizeof(isVisted));
        int N, M, ret = 0, minA = 0; // 최솟값
        cin >> N >> M;
        while (M--)
        {
            int a, b;
            cin >> a >> b;
            pq.push({a, b});
        }
        while (!pq.empty())
        {
            book cur = pq.top();
            pq.pop();
            if (minA < cur.first)
                minA = cur.first;
            else if (minA + 1 <= cur.second)
            {
                pq.push({minA + 1, cur.second});
                continue;
            }
            else
                continue;
            if (!isVisted[minA])
            {
                isVisted[minA] = true;
                ret++;
            }
        }
        cout << ret << "\n";
    }
    return 0;
}

풀이

최솟값을 갱신해가며 bool 배열을 확인해간다. 만약 최솟값보다 작거나 같으면서 1을 더한 것보다 b의 값이 크다면 a의 값을 최솟값에서 1을 더한 것으로 다시 갱신하는 방법을 사용하였다.
다른 사람의 풀이를 보니 크게 2개로 나뉘었다.

1. b를 작은 순으로 하여 푸는 방법

만약 다른 방법을 찾으려 했다면 이 방법을 사용했을 것이다.

2. 이분 매칭으로 푸는 방법

이분 매칭에 대해서 처음 들은 것 같다. 'N이 필요 없는 데 왜 있지?'라는 생각이 들었는데 이분 매칭을 의도한 부분도 있어서 주어진 거였다. 몇 번 더 만나보면 익숙해질 것 같다.