[백준 9576] 책 나눠주기 (C++)

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

문제

---

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

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

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

 

입력

---

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 a_i, b_i가 주어진다. (1 ≤ a_i ≤ b_i ≤ N)

 

출력

---

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

 

문제 풀이

---

회의실 문제와 유사한 그리디 문제.

책의 각 번호마다 책을 줄 수 있는지를 저장하는 canGive 배열을 만들어 체크한다.

b 오름차순으로 정렬한 후, a~b 범위 내에서 반복문을 이용해 줄 수 있는 가장 작은 번호를 찾아 줄 수 있다면 canGive 배열에 체크한 후 정답 count를 1 증가시키면 된다.

 

아래는 코드.

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

bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
	if (p1.second < p2.second)
	{
		return true;
	}
	else if (p1.second == p2.second)
	{
		return p1.first < p2.first;
	}
	else
	{
		return false;
	}
}

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

	int N, M, T;
	bool* canGive = new bool[1001];
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int answer = 0;
		cin >> N >> M;
		pair<int, int>* arr = new pair<int, int>[M];
		for (int i = 0; i < M; i++)
		{
			cin >> arr[i].first >> arr[i].second;
		}
		for (int i = 0; i < 1001; i++)
		{
			canGive[i] = false;
		}
		sort(arr, arr + M, cmp);
		for (int i = 0; i < M; i++)
		{
			for (int j = arr[i].first; j <= arr[i].second; j++)
			{
				if (canGive[j] == false)
				{
					canGive[j] = true;
					answer++;
					break;
				}
			}
		}
		cout << answer << "\n";
	}
	return 0;
}