BOJ 2295번: 세 수의 합

문제 설명

집합 안에 있는 수들 중 x,y,z 를 더해서 k가 될 때, k의 최대값 구하기

🔗 문제 링크

핵심 아이디어

• two 벡터에 모든 x + y를 저장
• x + y + z = k, 변형하면 x+y = k - z가 되므로 two 벡터 안에 k - z를 만족하는 수가 있는지 내림차순으로 확인하고 찾으면 바로 종료

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a,a+n);
    
    vector<int> two;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            two.push_back(a[i] + a[j]);
        }
    }
    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])){
                cout << a[i];
                return 0;
            }
        }
    }
}

‼️ 주의할 점

• sort(a,a+n) 을 해야 a[i]-a[j]를 binary search에서 제대로진행이 가능함!
• 선형 탐색 O(N)에 비해 이분 탐색은 O(logN)이므로 빠름
• x, y, z, k가 서로 같아도 됨! (중복도 허용)