B1931

개요

백준 문제 1931번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 150분
https://www.acmicpc.net/problem/1931

문제

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

코드

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

int N;
vector<pair<int,int>> v;
vector<pair<int,int>> startV;

void wrongSolve()
{
	cin >> N;
	int buf1,buf2,count = 1;
	for(int i=0;i<N;i++)
	{
		cin >> buf1 >> buf2;
		startV.push_back({buf1,buf2});
	}		
	sort(startV.begin(),startV.end());

	int selConfStart = startV[0].first;
	int selConfEnd = startV[0].second;
	//cout << "시작 : " << selConfStart << " " << selConfEnd << endl;

	for (int i = 1; i < startV.size(); ++i)
	{
		//지금 제일 작은 애
		//하이재킹
		if(selConfEnd > startV[i].second)
		{
			selConfStart = startV[i].first;
			selConfEnd = startV[i].second;
			//cout << selConfStart << " " << selConfEnd << endl;
		}
		//종료
		else if(selConfEnd <= startV[i].first)
		{
			selConfStart = startV[i].first	;
			selConfEnd = startV[i].second;
			count++;
			//cout << selConfStart << " " << selConfEnd << endl;
		}
	}
	cout << count;



}

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
	return (a.second < b.second);
}

void rightSolve()
{
	cin >> N;
	int buf1,buf2;
	int count = 0;
	for(int i=0;i<N;i++)
	{
		cin >> buf1 >> buf2; 
		v.push_back(make_pair(buf1,buf2));
	}
	sort(v.begin(),v.end());
	sort(v.begin(),v.end(),sortbysec);
	int min = v[0].second;
	count++;
	for(int i=1;i<N;i++)
	{
		if(v[i].first >= min)
		{
			min = v[i].second;
			count++;
		}
	}

	cout << count;
}



int main()
{
	wrongSolve();

}

풀이

1. 시작 시간으로 정렬
2. 두가지 경우로 나눠서 생각
3. 1 더 나은 (더 빨리 종료하는) 회의가 있으면 하이재킹
4. 2 회의가 종료됐다면 카운트

배울 점, 메모

위 두가지 접근은 처음부터 생각하는데 어려움이 없었다.
그러나 코드 구현상에서 문제의 몇가지 조건에 맞지않는 등이 있어서 실패를 많이 했다
하지만 다음날 다시 천천히 구현하니 꽤 쉽게 풀렸던 문제