[백준] 1931 회의실 배정

백준 1931 회의실 배정 문제 풀이입니다.

이 문제는 그리디 알고리즘을 분류 되있긴 하지만 시간을 생각해야 하는 문제입니다. 총 가짓수가 100000이기 때문에 만약 완전탐색으로 접근한다며 무조건 시간초과가 날 수밖에 없습니다.

따라서 저는 처음에 제가 단순히 접근해본 dfs풀이는 다음과 같습니다.

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

#define MAX 100001
typedef pair<int, int> p;

int N, Result;

vector<p> conference; // 회의 순서대로 (짧은 순서대로) 

void dfs(int Cur_End, int Cnt, int idx) { // 끝나는 시간, 회의갯수 

	if (Cnt > Result) {
		Result = Cnt;
	}
	
	for (int i = idx + 1; i < N; i++) {
		if (conference[i].first >= Cur_End) {
			dfs(conference[i].second, Cnt + 1, i);
		}
	}

}



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

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		conference.push_back({ a,b });
	}

	sort(conference.begin(), conference.end());
	Result = 0;

	for (int i = 0; i < N; i++) {
		dfs(conference[i].second, 1,i);
	}

	cout << Result;
	
	return 0;
}

이처럼 접근한다면 나름 시간을 줄이겠다고 idx를 저장하였지만 최악에 경우 10만!이 되게됩니다.

따라서 다음으로 접근한 방법은 특정 조건으로 정렬을 시켜보자였습니다. 종료시간 기준으로 정렬을 한 뒤 그 종료시간에 맞는 시작 시간으로 접근한다면 결국 최대 결과가 나올 것이라 생각했기 때문입니다.

따라서 저는 우선순위 큐를 사용하여 정렬을 사용하였습니다. 정답 코드는 다음과 같습니다.

Source Code:

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

typedef pair<int, int> p;

int N, Result = 0;

struct cmp {
	bool operator()(p a, p b) {
		if (a.second == b.second) {
			return a.first > b.first;
		}
		return a.second > b.second;
	}

};

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

	cin >> N;

	priority_queue<p, vector<p>, cmp> pq;

	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		pq.push({ a,b });
	}

	p first = pq.top();
	pq.pop();

	Result++;
	int End = first.second;

	while (!pq.empty()) {
		p tmp = pq.top();
		pq.pop();
		if (End <= tmp.first) {
			Result++;
			End = tmp.second;
		}
	}

	cout << Result;
	
	return 0;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 이런 종류의 그리디 문제는 너무 어렵다. ex) 수학적 사고가 조금은 들어가야하는
• 뿐만 아니라 예외상황을 생각해야 하는 문제는 내가 너무 약하다는 것을 알 수 있었다.
• 분명 랭크는 실버2인데 거의 체감상 골드급이였다..
• 더 공부하자