글 읽기 - [C] 틀렸습니다, 시간초과

jaehoo1 5년 전 0

1, 2번 서브태스크는 성공했습니다만

3, 4번에서 시간초과가 난다면 납득하겠습니다만

3번에선 틀렸습니다가 나오고 4번에선 시간초과가 나네요..?

왜 틀렸습니다가 3번에서만 나오는지 알 수 있을까요?

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

typedef struct
{
	int pos;
	int col;
}Point;
int cmp(const Point *a, const Point *b)
{
	if(a->pos<b->pos)return -1;
	else if(a->pos>b->pos)return 1;
	else	return 0;
}

int main(void)
{
	int N, i, res=0, j, bol;
	long long min;
	Point *arr;
	scanf("%d", &N);
	arr=(Point*)malloc(8*N);    //N의 갯수만큼 위치, 색에 대한 배열 동적할당
	for(i=0 ; i<N ; i++)
		scanf("%d%d", &arr[i].pos, &arr[i].col);
	qsort(arr, N, 8, (int(*)(const void *, const void *))cmp);    //좌표순 오름차순 정렬
	for(i=0 ; i<N ; i++)
	{
		j=i+1;	min=2000000000000000000;	bol=0;
		while(1)    //arr[i]의 뒤를 (선형)탐색_데이터가 많으면 당연히 시간초과
		{
			if(j>=N)break;
			if(arr[j].col==arr[i].col)
			{
				bol=1;
				if(min>abs(arr[j].pos-arr[i].pos))
					min=abs(arr[j].pos-arr[i].pos);
			}
			j++;
		}
		j=i-1;
		while(1)    //arr[i]의 앞을 (선형)탐색_데이터가 많으면 당연히 시간초과
		{
			if(j<0)break;
			if(arr[j].col==arr[i].col)
			{
				bol=1;
				if(min>abs(arr[j].pos-arr[i].pos))
					min=abs(arr[j].pos-arr[i].pos);
			}
			j--;
		}
		if(bol)res+=min;
	}
	printf("%d", res);
	return 0;
}

jaehoo1 5년 전 1

멍청했군요.. res가 int범위를 넘어설 수 있다는 것을 간과했습니다.

4번만 해결하면 되겠군요

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

문제

문제

출처

ICPC

[C] 틀렸습니다, 시간초과

jaehoo1 5년 전 0

jaehoo1 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말