[백준] 1931 - 회의실 배정

반응형

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

int main() {
	int n,s_t,e_t,first=0,last, room=1;
	vector<pair<int, int>> appointment;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s_t >> e_t;
		appointment.push_back(make_pair(e_t, s_t));
	}
	sort(appointment.begin(), appointment.end());
	last = appointment[0].first;
	for (int i = 1; i < n; i++)
	{
		if (appointment[i].second >= last)
		{
			room++;
			last = appointment[i].first;
		}
	}
	cout << room;

}

제가 생각한 풀이 방법은 일단 예약을 모두 마감시간 순서대로 정렬을 합니다. 그 후 처음에 방을 들어갈 그룹은 마감 시간이 가장 빠른 그룹 입니다. 

그 다음 부터는 마감시간에서 가장 가까운 예약 그룹이 회의방을 사용하도록 구상하였습니다.

 

이번 문제는 일반 배열을 사용해서 풀어 봤었는데 시간 초과로 인해 실패를 했었습니다.

 

그래서, 

 

백터와 알고리즘(sort)를 사용해서 상당히 간단하게 풀 수 있었습니다.

vector<pair<int, int>> 를 사용해서 2차원 배열처럼 백터를 사용할 수 있습니다.

 

다음으로 for 문으로 입력을 시작 시간과 끝나는 시간을 받고 

.push_back() 함수를 사용해서 make_pair() 로 appointment 변수에 저장해 줍니다.

 

여기서 회의 시작과 끝나는 시간을 반대로 저장한 이유는 이 다음에 

sort() 함수 때문입니다.

 

sort는 2차원 배열 특성상 1차원 배열에 저장된 값을 기준으로 정렬이 되기 때문에  회의 마감시간 기준으로 정렬을 하려면 배열에 반대로 저장을 해야 합니다.

 

그 후 time 변수에 마감 시간이 가장 빠른 그룹에 시간을 저장 한 후, for 문을 돌면서 마감시간과 가장 가까운 시작 시간을 갖고 있는 그룹을 회의에 배정한 후, 마감 시간을 다시 초기화 해 줍니다.

 

---

#include <algorithm>
#include <iostream>
// #include <utility>

using namespace std;
struct pt {
  int first;
  int second;
};
int main() {
  cin.ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  pt mt[N];

  for (int i = 0; i < N; ++i) {
    cin >> mt[i].first >> mt[i].second;
  }
  sort(mt, mt + N, [](pt &a, pt &b) {
    return (a.first < b.first)  ? true
           : a.first == b.first ? a.second < b.second
                                : false;
  });
  int n = 1;
  int u = mt[0].second;
  for (int i = 1; i < N; ++i) {
    if (mt[i].first < u && u <= mt[i].second) continue;
    if (u <= mt[i].first) ++n;
    u = mt[i].second;
  }
  cout << n;
}

다른 사람의 코드입니다.

이번 문제는 정말 다양한 풀이 방법이 있었습니다.

이분 같은 경우는 구조체를 사용해서 회의 시작 시간과 끝나는 시간을 저장했습니다.

 

cin.ios::sync_with_stdio를 사용해서 입력 시간을 줄이려고 하셨습니다.

for문으로 구조체에 각 시간을 저장하셨습니다.

그 다음 sort 함수에서 return 문에 삼항문으로 오름차순 정렬을 하셨습니다.

그 다음은 같은 로직으로 배정 반호를 계산하셨습니다.