[백준/BOJ] 백준 9576번 : 책 나눠주기

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

9576번: 책 나눠주기

 

회의실 배정 문제와 유사하게, 필요한 책의 범위 들을 범위가 끝나는 게 짧은 것 순으로 정렬하고, 정렬된 순서로 그리디 하게 책을 배정하여 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int tc;
int n, m;
int book_check[1005];
vector<pair<int, int>> range; //학생이 원하는 책 번호 (a~b)를 (b,a) 순으로 저장
vector<int> results;

void pre() {
	range.clear();
	for (int i = 0; i < 1005; i++) {
		book_check[i] = 0;
	}
}

//그리디로 문제 해결

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++) {
		pre();

		cin >> n >> m;

		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;

			range.push_back(make_pair(b, a));
		}

		//(a~b)범위에서 b 오름차순, a 오름차순 조건으로 정렬
		//회의실 배정 문제와 유사하게, 범위가 끝나는게 더 짧은것 우선 배정 한다
		sort(range.begin(), range.end());

		int result = 0;
		for (int i = 0; i < range.size(); i++) {
			int a = range[i].second;
			int b = range[i].first;

			for (int j = a; j <= b; j++) {
				if (book_check[j] == 0) { //해당 책이 배분되지 않았을때
					//해당 책을 배분한다
					book_check[j] = 1;
					result++;
					break;
				}
			}
		}
		results.push_back(result);
	}

	for (int i = 0; i < results.size(); i++) {
		cout << results[i] << "\n";
	}

	return 0;
}