[C] 백준 - 1931번: 회의실 배정

3월 28일(화)-그리디 알고리즘(1931번)

1931번: 회의실 배정

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

typedef struct {
	int start;
	int end;
} meeting;

meeting arr[100001];

int compare(const void* a, const void* b)
{
	meeting m1 = *(meeting*)a;
	meeting m2 = *(meeting*)b;

	if (m1.end > m2.end)
	{
		return 1;
	}
	else if (m1.end == m2.end)
	{
		if (m1.start > m2.start)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		return 0;
	}
}

1. 입력받는 N개의 회의시작 / 회의종료 시점을 qsort를 이용해서 오름차순으로 정렬하고자했다

회의시작 / 회의종료 시점을 구조체를 이용해서 입력받는 것으로 방향을 잡았기때문에, compare 함수도 수정해야함

-> 이 과정에서 start값을 이용해서 먼저 정렬할 것 인지 / end값을 이용해서 먼저 정렬할 것 인지를 고민했다 

 

	int tmp = 0;
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (arr[i].start > tmp)
		{
			tmp = arr[i].end;
			count++;
		}
	}

2. qsort를 진행한 이후, 회의 최대 개수인 변수 count를 구하는 부분이다

이 과정에서 tmp에 새로운 arr[i].end 값을 넣으며 count++을 하는 조건은 arr[i].start 가 tmp보다 큰 경우로 작성했었다

-> 하지만 문제조건을 다시 살펴보면, 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다고 명시했다

-> 즉 arr[i].start 값과 tmp값(이전의 end값)이 같은 경우에도 count를 올려주어야한다

-> 따라서 if (arr[i].start >= tmp)로 수정

-> 최종적으로 성공

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

typedef struct {
	int start;
	int end;
} meeting;

meeting arr[100001];

int compare(const void* a, const void* b)
{
	meeting m1 = *(meeting*)a;
	meeting m2 = *(meeting*)b;

	if (m1.end > m2.end)
	{
		return 1;
	}
	else if (m1.end == m2.end)
	{
		if (m1.start > m2.start)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &arr[i].start, &arr[i].end);
	}
	qsort(arr, N, sizeof(meeting), compare);

	int tmp = 0;
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		if (arr[i].start >= tmp)
		{
			tmp = arr[i].end;
			count++;
		}
	}

	printf("%d", count);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ