백준 9576 - 책 나눠주기

문제 설명

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1~N까지 번호가 매겨진 책이 있다.

a~b사이의 책을 받길 원하는 M명에 학생에게 최대한 많은 책을 나눠줘야 한다.

 

해당 문제는 회의실 배정 문제와 유사하다.

1~N까지 연속된 책을 최대한 많이 받을 수 있게 하는 것과 1~N시간 사이에서 회의실을 최대한 많이 사용하게 하는 것은 같은 논리이기 때문이다.

단, 회의실의 경우에서는 a~b를 모두 사용하지만 해당 문제는 a~b 중 하나만 선택해도 된다.

 

회의실 문제는 끝나는 시간(b)를 기준으로 정렬한 뒤, 가능한 요청의 개수를 세면 된다.

해당 문제의 풀이도 마찬가지이다.

 

이러한 방법이 최적해를 보장하는 이유는 b가 더 큰 경우를 먼저 처리한다고 가정해 보자.

그렇다면 b를 처리한 이후, 선택할 수 있는 경우는 b가 작은 경우를 먼저 처리했을 때보다 작거나 같다.

즉, b가 큰 경우를 선택하는 것보다 작은 경우를 선택하는 것이 유리하다.

 

따라서, b를 기준으로 정렬한 뒤, a부터 나눠주며 가능 여부를 판단하면 된다.

정렬할 때, a를 기준으로 같이 정렬한다면 시간을 더욱 줄일 수 있다.

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

[a, b] 안에서 아직 나눠주지 않는 책중 가장 작은 책을 고르기 때문이다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N, M;

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> T;

    while (T--)
    {
        cin >> N >> M;

        if (N == 1)
        {
            cout << 1 << "\n";
            continue;
        }

        vector<pair<int, int>> students;
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            students.push_back({ a,b });
        }

        sort(students.begin(), students.end(), cmp);

        vector<bool> checked(N + 1, false);
        int ans = 0;
        for (int i = 0; i < M; i++)
        {
            for (int j = students[i].first; j <= students[i].second; j++)
            {
                if (!checked[j])
                {
                    ans++;
                    checked[j] = true;
                    break;
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

---