백준 9576번: 책 나눠주기

[문제 링크]

9576번: 책 나눠주기

---

간단한 그리디 알고리즘 문제였다.

학생은 a이상 b이하인 책을 받을 수 있고, 줄 수 있는 책은 1번부터 N번까지 N개 존재한다.

 

두 학생이 있을 때 서로 a가 같다면 b가 더 큰 학생이 받을 수 있는 책의 범위가 더 넓기 때문에 b가 작은 학생순으로 낮은 번호의 책을 나눠주는 것이 항상 최적해를 보장한다는 것을 알 수 있다.

 

이를 구현하기 위해 b를 기준으로 오름차순 정렬하고, b의 값이 같을 경우 a가 더 작은 학생이 앞에 가도록 정렬하였다. 그리고 한 학생이 여러권의 책을 받을 수 없기 때문에 check 배열을 통해 책을 받았는지 여부를 확인하였다.

---

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

bool check[1000];

int Greedy(vector<pair<int, int>>& student, int N, int M)
{
	sort(student.begin(), student.end());

	int here = 0, cnt = 0;
	
	for (int book = 1; book <= N; book++)
	{
		for (int here = 0; here < M; here++)
		{
			if (student[here].second <= book && student[here].first >= book && !check[here])
			{
				cnt++;
				check[here] = true;
				break;
			}
		}
	}

	return cnt;
}

int main(void)
{
	int test_case;
	cin >> test_case;

	while (test_case--)
	{
		memset(check, 0, sizeof(check));

		int N, M;
		cin >> N >> M;
		
		vector<pair<int, int>> data(M);
		
		for (int i = 0; i < M; i++)
			cin >> data[i].second >> data[i].first;

		cout << Greedy(data, N, M) << endl;
		
		data.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 128 day