1. 문제설명

N권의 책에 1부터 N까지 정수 번호를 중복되지 않게 매겨 두었다.
M명의 학부생에게 두 정수 a, b를 적어 내라고 했다.
a 이상 b 이하인 책 중 남아있는 책 한권을 골라 그 학생에게 준다.
만약 모든 책을 이미 다른 학생에게 주고 없다면 그 학생은 책을 주지 않는다.
책을 줄 수 있는 최대 학생 수를 구하라

2. 알고리즘 설계

그리디 알고리즘 문제이다.
b가 큰 기준으로 정렬해서 순서대로 책을 부여한다.
책을 주지 못하면 카운팅하지 않는다.

3. 로직

우선순위 큐를 하나 선언하고, 해당 값에 b 값이 큰 순서대로 삽입한다.
a부터 b까지의 책 중 방문하지 않은 노드의 책이라면
- 방문했다고 표시한 후, 멈춘다.
- 책을 한권만 준다고 했기 때문
같은 방식으로 책을 부여하면 된다.

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct Cmp {
	bool operator()(const pii& a, const pii& b) {
		if (a.second == b.second) return a.first > b.first;
		return a.second > b.second;
	}
};

bool book[1001];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int TC; cin >> TC;
	while (TC--) {
		int n, m, ans = 0;
		cin >> n >> m;

		fill_n(&book[0], 1001, false);
		priority_queue<pii, vector<pii>, Cmp> pq;

		for (int i = 0; i < m; i++) {
			int s, e; cin >> s >> e;
			pq.push({ s, e });
		}

		while (!pq.empty()) {
			pii cur = pq.top();
			pq.pop();

			for (int i = cur.first; i <= cur.second; i++) {
				if (!book[i]) {
					book[i] = true;
					ans++;
					break;
				}
			}
		}

		cout << ans << '\n';
	}

	return 0;
}

5. 소감

b를 기준으로 정렬하려면 pair의 first에 b를 넣으면 정렬된다.
- 단, 이 방법은 cpp의 제공되는 자료구조 pair, tuple, int 등만 가능하다.
본인은 연습을 위해 모든 방법을 돌아가면서 사용한다.

구조체로 선언하는 경우 별도의 작업을 거쳐야한다.

// compare 함수 구현
struct Cmp {
  bool operator()(const pii &a, const pii &b) {
      return a.second > b.second;
  }
}

// 구조체 안 operator 정의
struct Node {
  pii cur;

  Node(int a, int b) {
      cur.first = a;
      cur.second = b;
  }

  bool operator<(const pii &other) {
      return cur.second > other.second;
  }
}

BOJ 9576. 책 나눠주기

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감