글 읽기 - [시간 초과] 알고리즘이 틀렸나요??

tjwjdgus12 4년 전 1

O(n^2 log n) 알고리즘이 시간내 작동한다고 해서 앞에 두 용액을 먼저 정하고 나머지 하나를 이진 탐색하여 찾는 방식으로 코드를 짰습니다.

그런데 2%에서 시간초과가 뜹니다 ㅠㅠㅠ 왜그럴까요

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

int N;

void io_boost() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

int binary_search(vector<ll> arr, int low, int high, ll val){
    if(low + 1 >= high)
        return (abs(arr[low]+val) < abs(arr[high]+val)) ? low : high;
    int mid = (low + high) / 2;
    if(arr[mid] + val > 0)
        return binary_search(arr, low, mid, val);
    else if(arr[mid] + val < 0)
        return binary_search(arr, mid, high, val);
    else
        return mid;
}

int main() {
    io_boost();
    cin >> N;
    vector<ll> sol(N);
    for(int i = 0; i < N; ++i)
        cin >> sol[i];
    sort(sol.begin(), sol.end());
    
    ll ans = 3999999999;
    int ans_i, ans_j, ans_k;
    for(int i = 0; i < N-2; ++i){
        for(int j = i+1; j < N-1; ++j){
            int k = binary_search(sol, j+1, N-1, sol[i]+sol[j]);
            int mix = abs(sol[i]+sol[j]+sol[k]);
            if(mix < ans) {
                ans = mix;
                ans_i = i;
                ans_j = j;
                ans_k = k;
            }
        }
    }
    
    cout << sol[ans_i] << " " << sol[ans_j] << " " << sol[ans_k];
    
    return 0;
}

luniro 4년 전 1

15번째 줄 arr를 참조형으로 안하면 호출될 때마다 배열 전체가 복사되기 때문에 O(n^3 lg n)이 되는거 아닌가요?

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

문제

문제

출처

ICPC

[시간 초과] 알고리즘이 틀렸나요??

tjwjdgus12 4년 전 1

luniro 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말