백준 9576 책 나눠주기 C++

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

9576번: 책 나눠주기

처음에는 범위가 작은 순으로 먼저 책을 주려했는데 반례가 있다는 걸 깨달았습니다.

 

책을 원하는 사람들의 정보에 대해 끝 번호가 오름차순이 되면서 끝 번호가 같은 경우 범위가 오름차순이 되도록하면 됩니다.

 

이렇게 하면 될 거 같아서 해봤는데 맞았네요... 그리디 느낌으로 접근해서 풀이를 어떻게 해야할지 모르겠습니다....

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
int a, b;
int t;
int result;

// 끝 번호 순으로 정렬
// 끝 번호 같으면 범위 작은 거 순으로 정렬
// 그리고 하니씩 체크

typedef struct info {
	int a;
	int b;
	int len;
}info;

vector<info>v;

void init()
{
	v.clear();
	result = 0;

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		info inf = { a, b, b - a + 1 };
		v.push_back(inf);
	}
}

bool compare(info& info1, info& info2) 
{
	// 끝 번호 같으면 길이 오름차순
	if (info1.b == info2.b) {
		return info1.len < info2.len;
	}

	// 나머지 끝 번호 오름차순
	return info1.b < info2.b;
}

void sort_vec()
{
	sort(v.begin(), v.end(), compare);
}

void check_max()
{
	bool check[1001];
	memset(check, false, sizeof(check));
	// 이미 줬으면 true, 아니면 false

	for (auto inf : v) {
		int start = inf.a;
		int last = inf.b;

		for (int num = start; num <= last; num++) {
			if (check[num] == false) {
				check[num] = true;
				result++;
				break;
			}
		}
	}
}

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

	cin >> t;

	while (t--) {
		init();

		sort_vec();

		check_max();

		cout << result << '\n';
	}


}