백준 2295 세 수의 합 / C++

문제 : 2295

풀이 point

간단하게 4중 for문을 생각할 수 있는데 그러면 시간 초과가 난다. 이 문제를 $O(N^2logN)$로 푸는 방법은 미리 더해놓은 값을 가지고 있는 것이다.

더해 놓은 값을 가지고 있다면 4중 for문을 돌릴 필요가 없다. $N^2logN$에 해결 가능하다.

풀이 방법

입력 받은 배열(arr)을 정렬한다.
$N^2$으로 값을 미리 값을 더해 둔 배열을 만든다.(two 배열) 그리고 이중 for문과 이진 검색을 통해 arr[l] - arr[k]가 two배열 안에 있는지 확인하면 된다.

코드

//백준 2295, 세 수의 합

#include <iostream>
#include <vector>
#include <algorithm>

int N;
int arr[1'005];
std::vector<int> two;

int main (){

    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    std::sort(arr, arr+N);

    for(int i{0}; i<N; ++i){
        for(int j{i}; j<N; ++j){
            two.push_back(arr[i] + arr[j]);
        }
    }

    std::sort(two.begin(), two.end());

    for(int l{N-1}; l>0; --l){
        for(int k{0}; k<l; ++k){
            if(binary_search(two.begin(), two.end(), arr[l]-arr[k])){
                std::cout << arr[l];
                return 0;
            }
        }
    }

    return 0;
}