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)

출력

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

예제 입력 1 복사

1

2 3

1 2

1 2

1 2

예제 출력 1 복사

2

---

문제 접근

  '이분 매칭'을 이용한 풀이를 사용하였다. 하지만 벡터를 초기화를 안하는 실수와 문제를 제대로 파악하지 않고 계속 괜한 곳만 고쳤다.

 

/* 책 나눠주기 */
#include <iostream>
#include <vector>
#define MAX 1001

using namespace std;

int t, n, m;
bool c[MAX];
int d[MAX];
vector<int> vec[MAX];

bool dfs(int x) {
	for(int i = 0; i < vec[x].size(); i++) {
		int t = vec[x][i];
		
		if(c[t]) continue;
		c[t] = true;
		
		if(d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}
	return false;
}

int main(void) {
	cin >> t;
	for(int z = 0; z < t; z++) {
		fill(d, d + MAX, 0);
		cin >> n >> m;
		for(int i = 0; i <= m; i++) {
			vec[i].clear();
		}
		for(int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			for(int j = a; j <= b; j++) {
				vec[i].push_back(j);
			}
		}

		int count = 0;
		for(int i = 1; i <= m; i++) {
			fill(c, c + MAX, false);
			if(dfs(i)) count++;
		}
		cout << count << endl;
	}
	return 0;
}