글 읽기 - c언어로 풀었는데 82%에서 틀리는데 반례 좀 찾아주세요!

sonson97 1년 전 0

시작 시간을 기준으로 오름차순으로 정렬하여 세는 방식으로 했는데 무슨 반례가 있는지 아무리 찾아봐도 못 찾겠네요 ㅠㅠ

#include <stdio.h>
#include <stdlib.h>
typedef struct _time
{
	int start;
	int end;
} Time;
void Com_Dev(Time* arr, int start, int end);
int Count_room(Time* arr, int count);

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

	Time* arr = (Time*)malloc(sizeof(Time) * cnt);
	for (int i = 0; i < cnt; i++)
	{
		scanf("%d %d", &arr[i].start, &arr[i].end);

	}
	Com_Dev(arr, 0, cnt-1);
	printf("%d", Count_room(arr, cnt));
	return 0;
}

void Com_Dev(Time* arr, int start, int end)
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	Com_Dev(arr, start, mid);
	Com_Dev(arr, mid + 1, end);
	int i = start, j = mid + 1;
	int temp = 0;
	Time* arr2 = (Time*)malloc(sizeof(Time) * (end - start + 1));
	while (i <= mid && j <= end)
	{
		if (arr[i].start <= arr[j].start)
		{
			arr2[temp++] = arr[i++];
		}
		else
		{
			arr2[temp++] = arr[j++];
		}
	}
	if (i > mid)
	{
		while (j <= end)
		{
			arr2[temp++] = arr[j++];
		}
	}
	else
	{
		while (i <= mid)
		{
			arr2[temp++] = arr[i++];
		}
	}
	for (int z = start, k = 0; z <= end; z++, k++)
	{
		arr[z] = arr2[k];
	}
	free(arr2);
	return;
}

int Count_room(Time* arr, int count)
{
	Time temp;
	temp.end = -1, temp.start=-1;
	int sum = 0;
	for (int i = 0; i < count; i++)
	{
		if (arr[i].start < temp.end)
		{
			if (temp.end > arr[i].end)
				temp = arr[i];
		}
		else
		{
			sum++;
			temp = arr[i];
		}
	}
	return sum;
}

adung7 1년 전 2

반례)

5
6 7
6 6
5 6
5 5
7 7

답:

adung7 1년 전 0

추가로 16번째줄에서 동적할당 하신 arr를 메인함수 종료전에 free해주셔야 합니다.

sonson97 1년 전 0

아 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어로 풀었는데 82%에서 틀리는데 반례 좀 찾아주세요!

sonson97 1년 전 0

adung7 1년 전 2

adung7 1년 전 0

sonson97 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말