[BaekJoon] 2295번 세 수의 합

• 이 글은 C++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 이 문제를 3중 for문을 사용하면 합을 구하고 합이 존재하는지 판단하여 시간복잡도가 O(N4)이기 때문에 시간초과가 발생하게 됩니다.
• 마지막 합이 존재하는지를 이분탐색을 사용하더라도 시간복잡도가 O(N3logN)이라서 시간초과가 불가피합니다.
• 문제를 해결하기 위해서는 이분탐색을 사용하되, 새로운 기법을 활용해야 합니다. 즉 2개의 숫자의 합을 하나의 배열을 만듭니다. 이 때의 시간복잡도는 O(N2)입니다. 이후 처음 배열의 두 개의 차이가 2개의 숫자의 합 배열에 존재하는지 확인하면 됩니다. O(N2logN)으로 해결할 수 있습니다.
• ex) a1+a2+a3 = a4 ->, a4 - a3 = a1+a2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int num;
    cin>>num;;

    int arr[1005];
    vector<int> two;
    for(int i=0;i<num;i++){
        cin>>arr[i];
    }
    sort(arr, arr+num);

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

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

    int result = 0;
    for(int i=0;i<num;i++){
        for(int j=i+1;j<num;j++){
            if(binary_search(two.begin(), two.end(), arr[j]-arr[i])){
                result = max(result, arr[j]);
            }
        }
    }

    cout<<result;
}