글 읽기 - 2381번문제 시간초과좀 해결해주세요. 진짜안되요

wlstn900 8년 전 0

이중for문을 돌려서 시간초과가 뜨는건데 이걸 어떻게 바꿔야하나요?

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

int main()
{
	int N,max=0,distance,i,j;
	int *a, *b;
	scanf("%d", &N);
	a = (int*)malloc(sizeof(int)*N);
	b = (int*)malloc(sizeof(int)*N);
	

	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &a[i], &b[i]);
	}

	for (i = 0; i < N; i++)
	{
		for (j = i + 1; j < N; j++)
		{
			distance = abs(a[i] - a[j]) + abs(b[i] - b[j]);
			if (max < distance)
				max = distance;
		}

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

iljimae 7년 전 0

이 문제의 최대 입력 크기가 50000이어서 이중 for문을 돌리면 시간초과가 납니다. 시간복잡도를 O(n)으로 줄이면 이 문제는 해결가능합니다.

아이디어가 떠오르지 않으면 http://blog.naver.com/programmer18/220794470677 를 참고하셔도 괜찮아요!! :)

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

문제

문제

출처

ICPC

2381번문제 시간초과좀 해결해주세요. 진짜안되요

wlstn900 8년 전 0

iljimae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말