글 읽기 - 2673 문제 접근 방법이 잘못된 것일까요?

hongpyo793 2년 전 0

문제를 보고 제가 이해했을 때,

각 현들의 시작점과 끝점(s, e)로 정렬하여 값을 받아온 다음 원 안에 있는 한개의 현을 기준으로 교차되지 않고, 좌/우에 위치하는 현의 갯수를 카운팅하도록

구현을 하였는데, 계속 틀렸습니다로 나오네요.

예제 조건 외에 몇 가지 경우를 다 넣어도 맞게 나오는거 같은데

어떤 부분을 놓치고 있는 걸까요??

#include "stdio.h"
#include "stdlib.h"

int N;
int ret;
int tmp;

typedef struct{
	int s,e;
}S_T;
S_T t[50+10];

int compare( const void* x, const void* y)
{
	S_T *px = (S_T*)x;
	S_T *py = (S_T*)y;
	
	if(px->s < py->s)	return -1;
	else if(px->s > py->s)	return 1;
	else	return 0;
}

int main()
{
	int temp;
	scanf("%d", &N);
	
	for(int i=0; i<N; i++)
	{
		scanf("%d %d", &t[i].s, &t[i].e);
		if(t[i].s>t[i].e)
		{
			temp=t[i].s;
			t[i].s=t[i].e;
			t[i].e=temp;
		}
	}
	
	qsort(t, N, sizeof(t[0]), compare);
	
	for(int i=0; i<N; i++)
	{
		tmp=0;
		for(int j=i; j<N; j++)
		{
			if(i==j)	continue;
			if(t[i].s<t[j].s&&t[i].e>t[j].e)	tmp++;
			else if(t[i].e<t[j].s)	tmp++;
		}
		if(ret<tmp)	ret=tmp;
	}
	
	if(ret==0)	printf("%d\n", ret);
	else	printf("%d\n", ret+1);
	
	return 0;
}

snrnsidy 2년 전 1

한 현을 기준으로 판단할 때, 한 현의 왼쪽 또는 오른쪽에 있는 현들 또한 겹치지 않아야 함을 만족해야 하는데, 생각하신 방법으로는 판단할 수 없어서 답보다 더 큰 값을 출력하게 됩니다

hongpyo793 2년 전 0

그건 생각을 못했네요. 답변 감사합니다.

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

문제

문제

출처

ICPC

2673 문제 접근 방법이 잘못된 것일까요?

hongpyo793 2년 전 0

snrnsidy 2년 전 1

hongpyo793 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말