글 읽기 - 1931번 예외처리

jangjs1216 5년 전 1

우선 병합정렬로 끝시간 기준 정리한뒤 그리디 알고리즘을 사용하는 방식으로 시도를 하였는데요,

앞에 보니까

2 2

1 2

이런 경우 때문에 끝시간으로 정렬하면 안된다고 하더라구요

그래서 같은경우 앞에걸 정렬해서 해결은 했는데,

같은 경우를 따로 저렇게 분류해주면 해결이 되어야 하는것 아닌가요?

대체 어디서 오류가 난것인지 궁금합니다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#include<stdio.h>

typedef struct arr{
	int start;
	int finish;
} kk;

kk dis[100001];
kk arr[100001];

void merge(int left, int right)
{
	int i,j,mid,k=left;

	if(left >= right)
		return;

	mid = (left + right)/2;
	i=left, j=mid+1;
	while(i <= mid && j <= right)
	{
		if(dis[i].finish < dis[j].finish)
		{
			arr[k].start = dis[i].start;
			arr[k++].finish = dis[i++].finish;
		}else{
			arr[k].start = dis[j].start;
			arr[k++].finish = dis[j++].finish;
		}
	}

	while(i <= mid)
	{
		arr[k].start = dis[i].start;
			arr[k++].finish = dis[i++].finish;
	}

	while(j <= right)
	{
		arr[k].start = dis[j].start;
		arr[k++].finish = dis[j++].finish;
	}

	for(i=left;i<=right;i++)
	{
		dis[i].start = arr[i].start;
		dis[i].finish = arr[i].finish;
	}
}

void divide(int left, int right)
{
	int mid = (left+right)/2;

	if(left >= right) return;

	divide(left,mid);
	divide(mid+1,right);
	merge(left,right);
}

int main(void)
{
	int n,t,i,j,temp,last=0,count = 0;
	scanf("%d",&n);

	for(i=0;i<n;i++)
	{
		scanf("%d %d",&dis[i].start,&dis[i].finish);
	}

	divide(0,n-1);

	for(i=0;i<n;i++)
	{
		if(dis[i].start == dis[i].finish)
		{
			count++;
			continue;
		}
		//시작 끝 같은경우 처리

		if(dis[i].start >= last)
		{
			last = dis[i].finish;
			count++;
		}
		//끝값 비교해주기
	}

	printf("%d\n",count);
}

seico75 5년 전 3

1 3

2 2

jangjs1216 5년 전 0

사랑합니다

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

문제

문제

출처

ICPC

1931번 예외처리

jangjs1216 5년 전 1

seico75 5년 전 3

jangjs1216 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말