[백준 1931] 회의실 배정

난이도

실버 I

📜문제

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

🌞풀이

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(pair<int, int> &a, pair<int, int> &b)
{
	if(a.second == b.second)
		return a.first < b.first;
	else return a.second < b.second;
}

int main()
{
	int N = 0;
	cin >> N;

	vector<pair<int, int>> v(N); // size를 입력해줄 수 있다

	for (int i = 0; i < N; i++)
	{
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end(), compare); // 사용자 정의 함수에 맞게 정렬

	int answer = 1;
	int last = 0;

	for (int i = 0; i < N-1; i++)
	{
		if (v[i + 1].first >= v[last].second)
		{
			answer++;
			last = i+1;
		}
	}
	cout << answer << "\n";

	return 0;
}

🔎설명

이 문제 같은 경우 정렬을 하는 기준 설정이 굉장히 중요하다. 서로 겹치지 않게 회의실을 최대로 사용하는 것이 문제이기 때문이다. 이때 정렬 기준을 두가지로 생각해볼수 있다.

1. 회의 시작 시간

시작시간을 기준으로 정렬을 했다고 생각했을 때 시작하는 시간은 알 수 있지만 빨리 시작해도 끝나는 시간을 알 수 없기 때문에 회의실 개수를 카운팅할 적절한 정렬이 아니다. 그림을 보면 첫번째 경우가 0에 시작을 했지만 6에 끝나서 두번째 시간인 (1,4) 보다 효율적인지 아닌지를 판단할 수가 없다.

1. 회의 종료 시간

제한된 시간 속에서 회의실을 많이 사용하는 것이 중요한데 종료시간을 기준으로 정렬을 하면 다음 사용시간보다 사용시간이 길 확률이 줄어든다.

예를 들어 첫번째 사용은 4에 끝나므로 아무리 길어도 4시간이다. 두번째 사용은 5에 끝나므로 아무리 길어도 5시간이다. 첫번째 사용이 아무리 길어도 두번째 사용을 다 사용하면 시간을 넘을 수 없다.

앞서 말했듯이 제한된 시간 속에서 회의실을 많이 사용해야하므로 시간을 잘 분배하는 것이 중요한데 확실히 끝나는 시간을 알면서 회의실을 배분하는것이 효율적이다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기