글 읽기 - 9426 중앙값 찾기 반례가 도저히 안나옵니다 ㅠㅠ..

h00201 6년 전 0

퀵정렬을 이용해서 풀려고 시도했는데 시간초과는 커녕 계속 틀렸다는 답만 나오네요..

물론 푼 것도 그렇게 잘 푼 것은 아니지만..

혹시 반례가 있는지 찾아주실 분 계신가요?

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
 
void swap(int *x, int *y) {
	int temp = *x;
	*x = *y;
	*y = temp;
	return;
}
 
void quicksort(int save[], int start, int end) {
 
	int pivot = save[(start + end) / 2], left = start, right = end;
 
	while(left <= right) {
		while(save[left] < pivot) left++;
		while(save[right] > pivot) right--;
		if(left <= right) {
			if(left != right) swap(save[left], save[right]);
			left++;	right--;
		}
	}
 
	if(start < right) quicksort(save, start, right);
	if(left < end) quicksort(save, left, end);
 
	return;
}
 
 
int main() {
	int enter1, enter2;
 
	scanf("%d %d", &enter1, &enter2);
 
	long long int sum = 0, k = 0;
 
 	int *save = new int[enter1];
 	int *save2 = new int [enter1];
 
	for(int i = 0; i < enter1; i++) {
		scanf("%d\n", &save[i]);
		save2[i] = save[i];
	}
 
	while(k + enter2 - 1 < enter1) {
		quicksort(save2, k, k + enter2 - 1);
		sum += save2[(k + enter2 - 1 + k) / 2];
		for(int i = k; i < k + enter2; i++) save2[i] = save[i];
		k++;
	}
 
	printf("%d\n", sum);
 
	delete[] save;
 
	return 0;
}

djm03178 6년 전 1

첫째로, %d는 int형을 출력하는 포맷이므로 sum을 출력하기에 적절하지 않습니다. %lld를 써야 합니다.

둘째로, 매번 정렬하고 원래대로 돌려놓는 이 방식은 큰 케이스에서 필시 시간 초과가 납니다. 간단히 시간 복잡도를 생각해보면 k개를 정렬(O(klgk))하고 복사(O(k))하는 작업을 O(n)번 반복해야 하니 O(nklgk) 정도로, 170억 가량이 되어 불가능합니다.

h00201 6년 전 0

흠.. 아무리 생각해봐도 최소 O(NK)까지밖에 생각이 안나네요.. 다른 방법에 대한 힌트가 혹시 있을까요?

djm03178 6년 전 1

다른 방법도 있는 듯하지만 제가 사용한 건 가운데 값을 항상 상수 시간에 뽑고 빠져나갈 것을 빼고 들어올 것을 넣는 데에 각각 lg k 시간이 걸리는 알고리즘이었습니다.

h00201 6년 전 0

상수시간에 뽑는다는건 첫 입력 때 중앙값을 이미 정리한다는 의미인가요?

그렇다면 아예 다른 방법을 생각해야 할 것 같은데.. segment tree같은걸 봐도 도통 이해가 안되네요..

그 외엔 아예 감도 안잡히고... 흑흑

djm03178 6년 전 1

참고로 테스트 케이스가 약해서인지는 모르겠지만 제가 예전에 매우 최적화된 O(nk) 코드로 988ms에 통과한 적이 있기는 합니다. 하지만 의도된 대로라면 확실히 난이도가 높은 문제라고 생각합니다.

h00201 6년 전 0

다른 글들을 검색하니 테스트 케이스가 약하다고 하시네요 대부분.. nk로 짜봤는데 시간이 오버되는걸 봐선 제가 짠 nk 자체도 최적화가 안 된 것 같네요 -_-;;

계속해서 빠른 답변 감사합니다. klgk 방법을 찾아봐야 할 것 같아요. 아마 군인이라 쉽진 않겠지만;

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

문제

문제

출처

ICPC

9426 중앙값 찾기 반례가 도저히 안나옵니다 ㅠㅠ..

h00201 6년 전 0

djm03178 6년 전 1

h00201 6년 전 0

djm03178 6년 전 1

h00201 6년 전 0

djm03178 6년 전 1

h00201 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말