백준 1931 - 회의실 배정

문제링크

• 백준 1931

오답을 이끌었던 문제 접근1 (시간초과)

• 각 회의를 시작시간을 기준으로 오름차순 정렬
• 앞에서부터 회의노드를 방문하면서 현재 회의노드의 끝나는 시간 이후에 진행하는 회의노드를 방문한다.
• 더 이상 방문할 수 있는 회의노드가 없는 경우 백트래킹을 통해 돌아온 후 다시 탐색한다.

잘못된 접근이었던 이유

• 백트래킹을 통해 접근하는 방법은 문제를 너무 어렵게 해석했던 것으로 판단된다.
• DFS의 재귀 구현에도 어려움을 겪으면서 의도했던 대로 동작하는 코드를 작성하지 못했다.

오답을 이끌었던 문제 접근2 (시간초과)

• 반복문을 통해 접근하였으나, 반복문 중첩을 통해 모든 경우의 수를 확인하려고 했던 점이 원인이었다.
• 최대 십만(100,000)개의 회의가 존재할 수 있는데 반복문 중첩은 최대 백만번의 비교연산과 대입연산이 필요하기 때문에 시간초과에 걸렸다.

문제 접근 방향 (Solution)

• 시작하는 시간이 빨라도 늦게 끝나면 최대 회의 수를 맞출 수 없으므로, 회의의 종료시간이 중요한 요소이다.
  1. 종료 시점에 대해서 오름차순 정렬
  2. 반복문을 통해 탐색하면서 if 탐색대상의 end_time <= 비교대상의 start_time then, end_time 갱신
  3. count += 1
  4. 배열의 끝에 도달할 때까지 2,3번 반복

런타임에러(Segfault)

• 할당되지 않은 메모리에 접근하려고 할 때 발생한다.
• sort 함수에서 cmp가 일관되지 않을 때 발생할 수 있다고 한다.

구현 결과

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

typedef struct _meet
{
	int start;
	int end;
} Meet;

int N;
vector<Meet> v;

bool cmp(Meet m1, Meet m2)
{
	if (m1.end != m2.end)
		return m1.end < m2.end;
	else if (m1.end == m2.end)
		return m1.start < m2.start;
}

int proc()
{
	int count = 1; // 처음에 회의는 하나
	int end_time = v[0].end;

	for (int i = 1; i < v.size(); i++)
	{
		if (end_time <= v[i].start)
		{
			end_time = v[i].end;
			count++;
		}
	}

	return count;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N;
	Meet tmp;
	for (int i = 0; i < N; i++)
	{
		cin >> tmp.start >> tmp.end;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end(), cmp); // N개의 회의
	int ans = proc();

	cout << ans << endl;
	return 0;

}