백준 2295 세수의합 c++ // 이분탐색 발상

https://www.acmicpc.net/problem/2295

2295번: 세 수의 합

1. 이진탐색 발상

nC2들의 합배열 : two

a를 탐색(n^2) * 이진탐색(lgN)

부분합을 구한후, 이진탐색을 하라!!!

 

2.의사코드

a[i]+a[j]+a[l]=a[k] 인 k 의 최대값 찾기

two(a[i]+a[j])==a[k]-a[l]인 k의 최대값 찾기!

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,m,a[1004],ret;
vector<ll> two;
set<int> s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for(int i=0;i<n;++i){
        for (int j = i; j < n; ++j) {
            two.push_back(a[i] + a[j]); //nC2의 합들
        }
    }
    sort(a,a+n);
    sort(two.begin(), two.end());
    
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (binary_search(two.begin(), two.end(), a[i] - a[j])) {
                ret = max(ret, a[i]);
            }
        }
    }
    cout << ret;
    return 0;
}