*[백준][9576] 책 나눠주기

www.acmicpc.net/problem/9576

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개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

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

 

해결방법

틀린 방법 : 시작 시간을 오름차순으로 정렬하여 앞에서부터 책을 나눠주는 방식으로 접근하였으나, 아래와 같은 예제를 해결 할 수 없었다. 

N = 5, M = 4 [(1, 4), (1, 4), (1, 4), (2, 2)] 이면, 1, 2, 3을 앞에서부터 나눠주게되어 (2, 2) 학생에겐 책을 줄 수 없게 되었다.

 

해결 방법 : 끝나는 시간을 오름차순으로 정렬하고 나눠주지 않은 책 중 가작 숫자가 적은 책부터 나눠주었다.

N = 5, M = 4 [(2, 2), (1, 4), (1, 4), (1, 4)] 으로 정렬이 되어, 2, 1, 3, 4 숫자의 책을 나눠 줄 수 있게 되었다.

 

소스코드

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;

bool cmp(pair<int, int>& a, pair<int, int>& b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}
int main()
{
	int tc;
	vector<pair<int, int>> info;
	int books[1001] = { 0, };
	scanf("%d\n", &tc);
	for (int i = 0; i < tc; i++) {
		int N, M;
		scanf("%d %d", &N, &M);
		info.clear();
		memset(books, 0, sizeof(books));
		for (int j = 0; j < M; j++) {
			int a, b;
			scanf("%d %d", &a, &b);
			info.push_back(make_pair(a, b));
		}
		sort(info.begin(), info.end(), cmp);
		int answer = 0;

		for (int j = 0; j < M; j++) {
			int start = info[j].first;
			int end = info[j].second;
			for (int k = start; k <= end; k++) {
				if (books[k] == 0) {
					books[k] = 1;
					answer++;
					break;
				}
			}
		}
		printf("%d\n", answer);
	}
}

결과