[C++] 1931: 회의실 배정

쩡우·2022년 11월 19일
1

BOJ algorithm

목록 보기
2/65

1931번: 회의실 배정 (acmicpc.net)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

풀이

처음엔 회의의 시작 시간끼리 비교하려고 생각해서 너무 복잡했는데, 끝나는 시간을 기준으로 생각하니 이지한 문제였다.
c로 문제를 풀 때에는 2개의 값을 하나로 묶기 위해서 2 x n의 2차원 vector나, 값 2개짜리 구조체의 배열을 사용했었는데 c++에 'pair'라는 완전 편리한 자료형이 있어서 사용해보았다.

먼저 input_data() 함수로 값을 입력받고, 입력받은 값을 pair(int, int)의 vector에 넣어준다.
그 후 vector를 정렬해주는데, 그냥 sort(rooms.begin( ), rooms.end( )) 를 하게 되면 vector에 들어 있는 pair의 first를 기준으로, first가 같을 경우 second를 기준으로 오름차순 정렬을 한다.
하지만 나는 회의의 종료 시간을 기준으로 정렬을 해야 하기 때문에, compare( )함수를 새로 만들어 주었다. 처음 입력을 받을 때 회의 시간 시간과 종료 시간을 pair에 반대로 입력해도 되지만, 더 직관적으로 풀고 싶어서 ㅎ-ㅎ

새로 정의한 compare( )함수 ->

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

second끼리 서로 같을 때만 first끼리 비교하고, 다를 때는 second끼리 비교한 값이 리턴되도록 했다.

그렇게 vector를 정렬하고 count_meeting( )함수를 실행한다.
count_meeting( )에서는 now_endtime을 0으로 세팅해준 후에 모든 pair를 확인한다.
어떤 회의의 시작시간 값이 now_endtime보다 크면, 그 회의의 종료시간을 now_endtime에 갱신하고 count를 1 늘려준다. 종료시간 -> 시작시간을 기준으로 오름차순 정렬했기 때문에 다음 갱신에 사용된 회의가 최적조건이다.

코드

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

using namespace std;

vector<pair<int, int>>	rooms;
int	n;

void	input_data(void);
int		count_meeting(void);
bool	compare(const pair<int, int> a, const pair<int, int> b);

int	main(void)
{
	input_data();
	sort(rooms.begin(), rooms.end(), compare);
	int result = count_meeting();
	cout << result;

	return (0);
}

void input_data(void)
{
	int start, end;
	cin >> n;
	
	int i = -1;
	while (++i < n)
	{
		cin >> start >> end;
		rooms.push_back(make_pair(start, end));
	}
}

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

int	count_meeting(void)
{
	int len = rooms.size();
	int	now_endtime = 0, count = 0;
	int	i = -1;

	while (++i < len)
	{
		if (now_endtime <= rooms[i].first)
		{
			now_endtime = rooms[i].second;
			count++;
		}
	}
	return (count);
}

야호!!😀😀

profile
Jeongwoo's develop story

1개의 댓글

comment-user-thumbnail
2022년 11월 20일

이지한 문제였다니..
귀여워요 ^_^

답글 달기