백준1931번. 회의실배정(C언어)

백준 알고리즘 1931번 회의실 배정 문제입니다.

자세한 문제는 사진을 읽어보시기 바랍니다.

https://www.acmicpc.net/problem/1931

1931번: 회의실배정

 

접근방법

일단 기본적인 접근방법을 몇 가지 생각해봅시다.

회의를 특정한 순서로 정렬한 뒤, for문을 사용해 각 요소가 조건에 맞으면 카운트를 증가시킨다.

먼저 이런 방법을 생각해봤는데, 그럼 어떻게 이를 정렬해야 할까요?

 

먼저 중점적으로 생각할 부분은 시간이기 때문에, 시작시간, 소요시간, 종료시간으로 생각해봅시다.

단순히 생각했을 때, 시작시간 중심으로 정렬하면 간단할 것 같습니다.

하지만 아무리 빨리 시작해도 소요시간이 길어 늦게 끝난다면 많은 회의를 진행하지 못할 것입니다.

 

그렇다면 소요시간으로 생각해봅시다. 소요시간 중심으로 정렬하게 되면,

회의 순서가 뒤죽박죽이 되기 때문에 최대 횟수를 구할 방도가 없습니다.

 

마지막으로 종료시간으로 생각해봅시다. 회의가 먼저 끝나면

그만큼 더 많은 회의를 진행할 수 있기 때문에, 이 방법이 가장 적절할 것 같습니다.

이런 상황에 어떤 방법을 쓰는 게 가장 좋은지 잘 모르겠다면, 예제를 활용하시면 됩니다.

예제를 사용해서 어떤 순서로 정렬했을 때 가장 많은 경우의 수가 나오는지 생각해봅시다.

 

시작시간으로 정렬한다면 정렬 순서는

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

이처럼 정렬이 될 텐데, 가장 앞의 요소부터 순서대로 회의를 시작하면, 최대 3개의 회의가 가능합니다.

소요시간은 미리 말했던 대로 순서가 뒤죽박죽이 되기 때문에, 정렬하는 의미가 없습니다.

그럼 끝나는 시간순으로 정렬해볼 텐데, 이는 예제 입력이 이미 정렬된 상태로 입력되었습니다.

결과는 보이는 대로 4개의 회의를 진행할 수 있습니다.

 

그럼 이제 이 방법으로 문제를 풀 때, 종료시간을 중심으로 오름차순 정렬할 텐데,

종료시간이 같다면 어떡할까요? 처음엔 빨리 시작하는 회의가 당연히 좋다고 생각했었는데,

그렇지 않았습니다.

위의 두 그림을 보면 시작시간을 중심으로 오름차순, 내림차순 중 어떻게 정렬해도

사실상 결과는 동일합니다. 그렇다면 종료시간이 같으면 아무렇게나 정렬해도 되느냐?

절대 그렇지 않습니다. 그 이유는 이 문제는 현실이 아닌 알고리즘이기 때문입니다.

이게 대체 무슨 소리냐? 예를 들어 설명해보겠습니다.

 

현실에선 오후 1시에 회의를 시작해서 오후 1시에 종료하는 경우는 있을 수 없습니다.

하지만 알고리즘에선 시간을 임의의 입력으로 받기 때문에 이런 경우가 가능합니다.

때문에 다음과 같은 상황이 발생할 수 있습니다.

이런 상황에서 시작시간이 늦은 순서로 정렬하면 최대 회의 수는 2개가 됩니다.

반대로 시작 시간이 이른 순서로 정렬하면, 최대 회의수는 마지막에 위치한 시작시간과

종료시간이 동일한 회의까지 포함하기 때문에 3이 됩니다.

이 문제는 가능한 최대 회의의 개수를 구하는 것이기 때문에 후자의 방법 쪽이 더 적절할 것입니다.

 

그럼 이제 코드를 통해서 알아보도록 할 텐데, 처음엔 중첩 for문을 사용해서 해결하려고 했었습니다.

하지만 회의의 개수 n이 최대 10만까지 정해질 수 있고, 시간제한이 2초이기 때문에

중첩 for문을 사용한 버블 정렬로는 시간 초과가 발생해서 실패했었습니다.

때문에 qsort를 사용한 퀵 정렬을 사용해서 문제를 해결해봤습니다.

typedef struct discussion {
	int start, end;
}Discussion;

먼저 회의의 시작시간과 끝나는 시간을 저장할 구조체의 형태를 선언해줍니다.

int compare(const void* a, const void* b) {
	const Discussion* n1, * n2;
	n1 = (const Discussion*)a;
	n2 = (const Discussion*)b;

	if (n1->end != n2->end) {
		if (n1->end < n2->end) {
			return -1;
		}
		else if (n1->end == n2->end) {
			return 0;
		}
		else {
			return 1;
		}
	}
	else {
		if (n1->start < n2->start) {
			return -1;
		}
		else if (n1->start == n2->start) {
			return 0;
		}
		else {
			return 1;
		}
	}
}

그 후 qsort에서 사용할 비교 함수인 compare를 정의합니다.

이는 위에서 말했던 대로 종료시간으로 정렬한 뒤, 종료시간이 같으면 시작시간으로 정렬합니다.

	int n, i, cnt = 0, t1, t2, last = 0;
	scanf("%d", &n);
	Discussion* dis;
	dis = (Discussion*)calloc(n, sizeof(Discussion));
	for (i = 0; i < n; i++) {
		scanf("%d %d", &t1, &t2);
		dis[i].start = t1;
		dis[i].end = t2;
	}

main함수에선 회의의 개수인 n을 입력받고, n의 크기에 맞춰서 구조체 포인터 배열에

calloc을 사용해 메모리를 할당해줍니다. 이를 배열처럼 활용할 겁니다.

그 후 n의 개수만큼 각 구조체 배열에 시작시간과 종료시간을 대입합니다.

qsort(dis, n, sizeof(Discussion), compare);
	for (i = 0; i < n; i++) {
		if (dis[i].start >= last) {
			cnt++;
			last = dis[i].end;
		}
	}
	printf("%d", cnt);
	free(dis);
    	return 0;
}

이 구조체를 qsort를 사용해 정렬하고, 다음으로 회의 개수를 계산하면 끝입니다.

각 배열에 순서대로 접근하면서, 현재 요소의 시작시간이

마지막으로 끝낸 회의의 종료시간보다 크면 카운트를 하나 증가시켜줍니다.

마지막으로 값을 출력한 뒤, free를 할당해 dis의 메모리를 해제해주시면 끝입니다.

전체 소스코드는 아래에 있습니다.

#include<stdio.h>
#include<stdlib.h>

typedef struct discussion {
	int start, end;
}Discussion;

int compare(const void*, const void*);

int main() {
	int n, i, cnt = 0, t1, t2, last = 0;
	scanf("%d", &n);
	Discussion* dis;
	dis = (Discussion*)calloc(n, sizeof(Discussion));
	for (i = 0; i < n; i++) {
		scanf("%d %d", &t1, &t2);
		dis[i].start = t1;
		dis[i].end = t2;
	}
	qsort(dis, n, sizeof(Discussion), compare);
	for (i = 0; i < n; i++) {
		if (dis[i].start >= last) {
			cnt++;
			last = dis[i].end;
		}
	}
	printf("%d", cnt);
	free(dis);
    	return 0;
}

int compare(const void* a, const void* b) {
	const Discussion* n1, * n2;
	n1 = (const Discussion*)a;
	n2 = (const Discussion*)b;

	if (n1->end != n2->end) {
		if (n1->end < n2->end) {
			return -1;
		}
		else if (n1->end == n2->end) {
			return 0;
		}
		else {
			return 1;
		}
	}
	else {
		if (n1->start < n2->start) {
			return -1;
		}
		else if (n1->start == n2->start) {
			return 0;
		}
		else {
			return 1;
		}
	}
}