글 읽기 - 이 문제를 해결하려면 무엇을 공부해야하나요!

boffin 6년 전 0

ACM-ICPC 13334번 철로 문제를 풀었는데

결과로 시간초과가 나왔습니다.

어떤 공부를 해야할까요..

막막하네용

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

int main() {
	int n, d;
	int l[100000][2] = { 0 };
	int i,j,k;
	int max = 0, count=0;
	scanf("%d", &n);

	for (i = 0; i < n; i++) scanf("%d %d", &l[i][0], &l[i][1]);

	scanf("%d", &d);

	for (i = 0; i < n; i++) {
		if (abs(l[i][1] - l[i][0])>d) {
			l[i][0] = l[n - 1][0];
			l[i][1] = l[n - 1][1];
			n--;
			i--;
		}
	}
	for (i = 0; i < n; i++) {
		if (l[i][0]>l[i][1]) {
			j = l[i][0];
			l[i][0] = l[i][1];
			l[i][1] = j;
		}
	}

	//for (i = 0; i < n; i++)printf("%d %d\n", l[i][0], l[i][1]);

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			if (l[j][0] >= l[i][0] && l[j][1] <= (l[i][0]+d))count++;
		
		if (max < count)max = count;
		count = 0;

		for (k = 0; k < n; k++)
			if (l[k][0] >= (l[i][1] - d) && l[k][1] <= l[i][1])count++;

		if (max < count)max = count;
		count = 0;
	}

	printf("%d", max);

}

chogahui05 6년 전 1

이 문제 말이죠.

비슷한 질문이 있었고, 제가 답변을 했던 걸로 기억하는데요..

일단 잘 안 풀리신다면 질답게를 찬찬히 먼저 보시는 게 좋아보이네요.

이 문제를 푸시려면 정렬과 우선순위 큐 (혹은 set)에 대해서 아시는 게 필요해 보여요.

boffin 6년 전 0

chogahui05 님 답변 감사드립니다!!!

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

문제

문제

출처

ICPC

이 문제를 해결하려면 무엇을 공부해야하나요!

boffin 6년 전 0

chogahui05 6년 전 1

boffin 6년 전 0

chogahui05 님 답변 감사드립니다!!!

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말