[C++] 백준 1931번 - 회의실 배정 문제

1. 문제

 

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

1931번: 회의실 배정

2. 논리 방식

 

해당 문제에서 회의 스케쥴을 표현하면 아래와 같다.

 

가장 최적의 경우로 회의실을 배정하는 과정을 생각해보았을 때, 아래와 같은 조건들을 만족시켜야 한다.

 

1) 선택한 회의 시간의 시작 시간 >= 직전에 시행된 회의가 끝나는 시간

선택한 회의 시간의 시작 시간과 직전에 시행된 회의가 끝나는 시간이 동일해도 상관없다는 걸 유의한다.

2) 가능한 회의들 중 소요 시간이 가장 짧은 회의. 즉, 회의가 끝나는 시간이 제일 빠른 것을 고른다.

 

결론적으로 이 문제의 핵심은 바로 회의 종료 시간에 있다. 종료 시간을 기준으로 주어진 회의 시간들을 정렬한 다음, 시작 시간이 전 회의의 종료 시간보다 같거나 크면 배정을 하면 된다. 시작 시간을 기준으로 배정을 한다면 회의 소요 시간 조건을 고려하지 못하기 때문에 종료 시간을 기준으로 한다. (가령, 회의 시작은 0시에 했지만 끝나는 시각이 14시라면 최적의 경우를 구하지 못할 수 있다.)

더불어 또 중요한 점은 끝나는 시간이 동일한 땐 시작 시간이 빠른 순대로 정렬해야 한다는 점! 그래야지만 소요 시간 조건을 완벽하게 만족할 수 있다.

 

📌 위 사고가 어떻게 맞는지 알 수 있을까?

이 사고가 맞는지는 귀류법을 통해 알 수 있다. 만약 위 그림에서 첫 번째 회의를 선택했고, 이 후 두 번째 회의를 골라야 하는 상황이라고 가정해보자. 현재 우리가 세운 가설은 '가능한 회의들 중 가장 먼저 끝나는 회의를 선택하는 방법이 가장 최적의 방법이다' 이므로 1~3시 회의 이후 5~7시 회의를 선택해야 한다. 이런 식으로 하면 총 4개의 회의를 배정할 수 있다.

이때 가설을 거짓이라 가정해 '가장 먼저 끝나는 회의를 선택하지 않아도 더 많은 회의를 배정할 수 있다.'라고 해보자. 그리고 5~8시 회의를 두 번째 회의로 잡았다고 한다면 세 번째로 12~13시 회의를 잡을 수 있다. 5~8시 회의를 선택한다고 하면 총 3개의 회의밖에 배정하지 못한다. 고로 귀류법에 의해 우리가 원래 세운 가설은 최적의 결과를 낸다는 것을 알 수 있다.

참고: https://blog.encrypted.gg/975

 

 

3. 코드

#include <bits/stdc++.h>
using namespace std;

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

	int cnt = 0;
	int result = 0;
	int t = 0; //t는 전 회의 끝나는 시간
	pair<int, int> sch[100005];
	
	cin >> cnt;

	for (int i = 0; i < cnt; i++) {
		cin >> sch[i].second; 
		cin >> sch[i].first; 
	} //(끝나는 시간, 시작 시간)으로 저장된 상황

	sort(sch, sch + cnt); //끝나는 시간 기준으로 정렬

	for (int i = 0; i < cnt; i++) {
		if (sch[i].second >= t) {
			result++;
			t = sch[i].first;
		}
	}

	cout << result;
}

 

4. 이슈 및 배운점

 

이슈

• if(sch[i].second >= t) 부분에서 처음에 그냥 '>' 이렇게 썼다가 틀렸다. 맞은 것 같아도 끝까지 꼼꼼하게 코드 보기!

 

배운 점

• 처음에 접근한 방식은 선택한 회의 시간의 시작 시간이 직전에 시행된 회의가 끝나는 시간보다 짧으면 되지 않을까? 생각하고 배열을 이용해 회의 시간 스캔 받고, 비교하고, 스캔하고, 비교하고... 방식으로 구현했다. 소요 시간이라는 조건은 간과하고 코드를 짠 것이다. 문제를 풀 때는 중요한 자세는 급하게 접근하려 하지 말고 문제에 내포된 모든 조건들을 파악을 해야 함을 다시 한 번 배울 수 있었다.
• 내 풀이가 맞는지 확신이 들지 않는다면 귀류법도 사용해보도록 하자.