글 읽기 - 세 용액 질문입니다. ㅠ

donghy9508 6년 전 0

i와 j값을 고정시켜두고 그 mid를 이진탐색하는 알고리즘으로 짜서 시간복잡도는 O(N^2logN)입니다.

그래서 시간초과는 나지 않을것 같은데

i와 j값이 달라야하고 mid는 i,j와 달라야하기 때문에 이진탐색의 조건을 left+2<=right로 하였습ㄴ다.

그래서 시간초과는 나지 않는데 제출해보면 틀렸다고 나옵니다. 그래서 정올에 제출해보니까

15개 테스트케이중에서 7개 테스트 케이스는 통과하는데 나머지 8개 테스트 케이스를 통과를 못합니다,

이진탐색을 구현할때 그 절대값이 작은 쪽으로 가게 해야 될거같은데

제 조잡한 실력으로는 여기까지입니다,ㅠㅠ

도움 부탁드립니다.

#include<iostream>
#include<string.h>
#include<functional>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
long long arr[5000];
long long MIN = 1e9 * 3;
vector < long long > ans(3);
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			int left = i;
			int right = j;
			while (left + 2 <= right) {
				int mid = (left + right) / 2;
				if (abs(arr[left] + arr[right] + arr[mid])<MIN) {
					ans[0] = arr[left];
					ans[1] = arr[right];
					ans[2] = arr[mid];
					MIN = abs(arr[left] + arr[right] + arr[mid]);
				}
				if (arr[mid] + arr[left] + arr[right] >= 0) {
					right = mid - 1;
				}
				if (arr[mid] + arr[left] + arr[right] < 0) {
					left = mid + 1;
				}
			}
		}
	}
	sort(ans.begin(),ans.end());
	for (int i = 0; i < ans.size(); i++) {
		printf("%lld ", ans[i]);
	}

}

chogahui05 6년 전 1

의도대로 푸시려면

arr[i] + arr[j] = k라고 할 때

[i+1, j-1] 구간에서 -k와 제일 가까운 수를 뽑아야 하는 것 아닌가요? 그런데 이건.. upper_bound나 lower_bound 정도로 쉽게 해결 가능하고요.

중간 처리를 잘못 하셔서 틀렸습니다가 뜬 거 같아요.

보통 ~와 가까운 수를 찾아라. 이러는 경우는

이웃한 항들도 같이 검사하는 경우가 있거든요.

그리고 O(n^2logn)으로는 5000*5000*13=3억 얼마..

시간초과가 날 거 같네요.

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

문제

문제

출처

ICPC

세 용액 질문입니다. ㅠ

donghy9508 6년 전 0

chogahui05 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말