개요

[링크]백준 1931번: 회의실 배정

각 회의의 시작 시간과 끝나는 시간을 입력값으로 준다.
각 회의가 겹치지 않도록 하면서 회의실을 최대한 많이 사용할 수 있는 갯수를 구하라.

접근 방식

• 처음으로 구현한 방식은 pair<int,int> 를 이용하여,
  algorithm헤더의 sort를 이용해 시작시간, 종료시간을 정렬 후,
  시작 시간이 같은 pair에선 시작시간과 종료시간의 차이가 최소인 pair만 고르고,
  그 종료시간보다 큰 시작시간의 pair을 찾아서 반복하는 방법이였는데,
  예를 들어 (1,2)(3,10)(4,5)(5,6) 이렇게 들어오면
  답이 (1,2)(3,10) 두 개로 끝나버린다

• 두번째 방식은 재귀를 섞어서

//메인 함수에 solution 호출하는 부분
for (int i = 0; i < amount; i++) {
	solution(i, amount, 1);
}

//DFS방식으로 모든 경우의수일때 제일 큰 답 출력
void solution(int startIdx,  int& amount, int tempAns) {						//idx값 넣어주고, 그전 Second값 넣어주고, 총 갯수
	int temp_tempAns = 0;														//각 솔루션내에서 반복 돌때 그냥 tempAns넣어주면 
																				//한 솔루션 내에서 for문 돌때 tempAns가 계속 누적합되버림
	if (amount == 1){															//startIdx+1이 amount보다 작을때만 가동하므로 amount=1일땐 따로 처리함
		ans=1;															
		return;
	}
	if (startIdx > amount) {													//만약 startidx>amount일때 return	
		return;

	}

	for (int i = startIdx+1; i < amount; i++) {									//각 솔루션내에서 반복문
		temp_tempAns = tempAns;													//temp_tempAns값에 넣어주고
		if (v[startIdx].second > v[i].first) continue;							//그다음 번째 first값이 지금 second값보다 작으면 패스
		else {
			temp_tempAns++;														//second보다 first가 작거나 같게된것이므로 답++
			ans = temp_tempAns > ans ? temp_tempAns : ans;						//진짜 답과 임시답 체크
			solution(i,amount,temp_tempAns);									//재귀
		}

	}
}

이렇게 작성을 했는데, 시간복잡도가 O(n^2)이라서
회의의 수가 10만개가 들어오면 100억번의 연산을 해야해서
시간초과가 뜬다.

• 세번째 방법
  그리디 알고리즘을 적절히 활용을 한 방법으로,
  키포인트는 시작시간에 포커스를 두는게 아니라
  종료시간에 포커스를 두는 것이다.
  종료 시간을 기준으로 제일 빠른것부터 선택을 하고
  그 다음으로 빠른 종료 시간 강의의 시작시간이랑 비교를 하고 이 스텝을 반복하면 O(n)의 시간복잡도로 가능하다.
  

코드

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

vector<pair<int,int>> v;

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

}

void input(int& amount) {
	int sTime=0, eTime = 0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> sTime >> eTime;
		v.push_back(make_pair(sTime, eTime));
	}
}
	
void solution(const int& amount) {																		//답 도출함수
	int currentSecond = 0, ans = 1;
	sort(v.begin(), v.end(),comp);															//정렬
	currentSecond = v[0].second;
	for (int i=1;i<v.size();i++)
	{
		
		if (v[i].first >= currentSecond) {
			ans++;
			currentSecond = v[i].second;	
		}
	}

	cout << ans;
}

int main() {
	int amount = 0;
	input(amount);
	solution(amount);
}

문풀후생

범위로 시간복잡도 계산도 안하고 DFS이용하려 하다가
시간초과가 떠서 민망했다.