[BOJ 9576] 책 나눠주기

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

9576번: 책 나눠주기

 

- 문제 요약

 

백준이는 방 청소를 하면서 필요 없는 N권의 전공 서적을 사람들에게 나눠주려고 한다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다.

백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다.

그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다.

만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

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

 

 

- 알고리즘 정리

 

문제를 보자마자 회의실 배정 문제랑 비슷하다는 생각이 들었습니다.

처음에는 그냥 a값을 기준으로 우선순위 큐에 넣어서 순서대로 책을 나눠주면 되지 않을까 했는데 반례가 존재했습니다.

 

반례)

1 1

1 3

2 2

 

위와 같이 넣어주는 경우 첫 번째에는 1번 책을, 두 번째에는 2번 책을 주게 될 것입니다.

이렇게 책을 나눠주면 세 번째 학생이 책을 받지 못합니다.

이를 아래와 같이 바꿔주면 3명이 모두 책을 받을 수 있습니다.

 

1 1

2 2 

1 3

 

그러므로 a값이 아닌 b값을 기준으로 우선순위 큐에 넣어서 책을 나눠주면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int t,n,m,result,a,b;
bool arr[MAX];
priority_queue<pair<int,int> >pq;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		result=0;
		cin>>n>>m;
		memset(arr,false,sizeof(arr));
		for(int i=0;i<m;i++){
			cin>>a>>b;
			pq.push({-b,-a});
		}
		while(!pq.empty()){
			b=-pq.top().first;
			a=-pq.top().second;
			pq.pop();
			for(int i=a;i<=b;i++){
				if(!arr[i]){
					arr[i]=true;
					result++;
					break;
				}
			}
		}
		cout<<result<<"\n";
	}
}

코드 제출 결과