의도대로 푸시려면
arr[i] + arr[j] = k라고 할 때
[i+1, j-1] 구간에서 -k와 제일 가까운 수를 뽑아야 하는 것 아닌가요? 그런데 이건.. upper_bound나 lower_bound 정도로 쉽게 해결 가능하고요.
중간 처리를 잘못 하셔서 틀렸습니다가 뜬 거 같아요.
보통 ~와 가까운 수를 찾아라. 이러는 경우는
이웃한 항들도 같이 검사하는 경우가 있거든요.
그리고 O(n^2logn)으로는 5000*5000*13=3억 얼마..
시간초과가 날 거 같네요.
donghy9508 6년 전
i와 j값을 고정시켜두고 그 mid를 이진탐색하는 알고리즘으로 짜서 시간복잡도는 O(N^2logN)입니다.
그래서 시간초과는 나지 않을것 같은데
i와 j값이 달라야하고 mid는 i,j와 달라야하기 때문에 이진탐색의 조건을 left+2<=right로 하였습ㄴ다.
그래서 시간초과는 나지 않는데 제출해보면 틀렸다고 나옵니다. 그래서 정올에 제출해보니까
15개 테스트케이중에서 7개 테스트 케이스는 통과하는데 나머지 8개 테스트 케이스를 통과를 못합니다,
이진탐색을 구현할때 그 절대값이 작은 쪽으로 가게 해야 될거같은데
제 조잡한 실력으로는 여기까지입니다,ㅠㅠ
도움 부탁드립니다.