4주차(그리디) - [C++]백준1931 회의실 배정

25 Mar 2022 in Study on Algorithm

백준1931 회의실 배정 링크

문제

예제 입력

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> arr;
int n, cnt = 0;

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

	cin >> n;
	int st, end;
	for (int i = 0; i < n; i++) {
		cin >> st >> end;
		arr.push_back({ end, st });
	}
	sort(arr.begin(), arr.end());

	int cur = 0;
	for (int i = 0; i < n; i++) {
		if (cur <= arr[i].second) {
			cnt++;
			cur = arr[i].first;
		}
	}
	cout << cnt;
}

설명

이 문제는 한 회의실에 회의를 배정해야 하는데 겹치지 않는 최대한의 회의의 수를 할당해주는 것, 즉 스케줄링하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 algorithm와 vector를 사용하여 구현했습니다. 각 회의에 대한 시작 시간과 종료 시간을 입력 받는데 pair로 종료 시간을 앞에 저장했습니다. 이렇게 한것은 회의가 끝이 나면 그것보다 이른 시점에서 시작한 것이니 먼저 확인해야하는 사항이 아니라서 종료 시간이 짧은 것을 기준으로 잡은 것입니다. 종료 시점에서 최선의 선택으로 다른 회의들의 시작 시점을 확인하며 최대한 회의를 배정합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과