[백준 2295번] 세 수의 합 (C++)

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

---

본 게시글은 바킹독님의 [바킹독의 실전 알고리즘] 0x13강 - 이분탐색을 참고하여 작성되었습니다.

 

세 수의 합 문제는 이분탐색으로 해결할 수 있습니다.

가능한 방법은 3가지가 있습니다.

• 4중 for문 이용하여 모든 경우의 수를 확인하는 방법, 시간 복잡도는 O(N⁴)
• 가능한 세 수의 합을 구하고, 각 합이 집합 U 안에 존재하는지 확인하는 방법, 시간 복잡도는 O(N³logN)
• sum[i] + a[j] = a[k]를 만족하는 a[k]의 최댓값을 구하는 방법, 시간 복잡도는 O(N²logN)
  (단, sum은 두 수의 합을 저장한 배열)

N이 최대 1,000이기 때문에 O(N²logN) 알고리즘을 이용하여 해결할 수 있습니다. 

 

solution은 아래와 같습니다.

• 가능한 두 수의 합을 구한다. 
• 이중 for문에서 이분탐색을 이용하여 sum 배열에서 arr[i] - arr[j]를 찾는다.
• arr[i]의 최댓값을 구한다.

⚠️ 이분탐색을 수행하는 sum 배열은 정렬되어 있어야합니다!

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int arr[1000];
vector<int> sum;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];

    for(int i = 0; i < n; i++)  // 가능한 두 수의 합을 구한다.
        for(int j = i; j < n; j++)
            sum.push_back(arr[i] + arr[j]);
    
    sort(arr, arr + n); // arr 정렬
    sort(sum.begin(), sum.end());   // 두 수의 합 벡터 정렬 (이분탐색을 수행하기 위해)

    for(int i = n - 1; i >= 0; i--){    // arr[i]의 최댓값을 구한다. (큰 값부터 확인하기 때문에 찾으면 바로 종료)
        for(int j = i; j >= 0; j--){
            int a = arr[i] - arr[j];  
            bool exist = binary_search(sum.begin(), sum.end(), a);  // 이분탐색 수행
            if(exist) {
                cout << arr[i] << "\n";
                return 0;
            }
        }
    }
}