백준 9576번 책 나눠주기

문제링크

문제 해설

접근법

새로운 예시를 하나 해결해보자.

3 3

1 3

1 2

1 1

1번을 요청하는 학생은 3명이지만, (1,1)의 범위를 가진 학생이 1번을 가져가야만 최대로 가져갈 수 있다.

3 3

3 3

2 3

1 3

3번을 요청하는 학생은 3명이지만, (3,3)의 범위를 가진 학생이 먼저 3번을 가져가야 한다.

학생이 원하는 범위가 클수록 선택의 폭은 넓어진다.

반대로 범위가 작을수록 선택의 폭은 줄어든다.

그렇다면 당연히 범위가 작은 학생부터 선택하도록 해야 한다.

그러나 단순히 범위가 작은 학생부터 가져가는 것은 아니다. 같은 번호 내에서 범위가 작은 학생부터 가져가야 한다.

그리디 알고리즘으로 문제를 해결할 수 있다.

풀이

1. 범위 배열을 b를 기준으로 오름차순 정렬한다.
2. b가 같다면 범위가 작은, 즉 a가 클수록 앞으로 오도록 정렬한다. (a의 내림차순)
3. 범위를 하나씩 확인하면서 책을 고르지 않았다면 고르고 다음 범위로 넘어간다. 골랐다면 고르지 않은 책이 나올 때까지 진행.

소스코드

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

using namespace std;


typedef pair<int, int> pi;
int n, m;
vector<pi> range;
bool visit[1001];

// 책 정렬
bool cmp(pi a, pi b) {
	if (a.second == b.second)
		return a.first > b.first;
	return a.second < b.second;
}

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

	int tc;
	int answer;
	cin >> tc;
	while (tc--) {
		memset(visit, 0, sizeof(visit));
        range.clear();
		answer = 0;
		cin >> n >> m;
		
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			range.push_back({ a,b });
		}
		
		sort(range.begin(), range.end(),cmp);
		
		for (int i = 0; i < m; i++) {
			// 책 고르기
			for (int j = range[i].first; j <= range[i].second; j++) {
				if (!visit[j]) {	// 고르지 않았다면 고르기.
					visit[j] = true;
					break;
				}
			}
		}
        // 골라진 책의 개수 확인
		for (int i = 1; i <= n; i++)
			answer += visit[i];
		
		cout << answer << "\n";
	}

	return 0;
}