[백준/Baekjoon] 2295 세 수의 합 C++ :: Binary Search

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

2295번: 세 수의 합

---

1. Logic

이 문제를 접근할 때 처음에는 이분탐색이 아닌 투포인터로 접근하려고 했었다. 입력이 1000개이기 때문에 시간복잡도를 맞춰야 했고  N^3으로는 풀지 시간내에 계산을 못한다. 적어도 N^2logN정도를 맞춰야 했다. 

 

이분탐색으로 가능했는데 이분탐색에 대한 로직은 

1. 입력 받은 수를 토대로 3개의 수 중 2개의 수를 합쳐놓은 sum 배열을 만든다.

2. (합친 수 - 다른 1개의 수) 가 배열 내의 가장 큰 수로 존재해야 한다.

3. 이분탐색을 통해 (합친 수 - 다른 1개의 수)가 있는지 찾는다.

 

(합친 수 + 다른 1개의 수)을 확인하는 방법은

먼저 수식으로 나타내 보자면숫자가 큰 순서대로  x+y+z = k가 되야한다.

배열내의 x, y, z를 합한 수가 배열 내의 있는 숫자 중 가장 큰 k로 되어야 한다. 

위의 식에서 z를 이항해 보면 x+y = k-z가 된다.

우리는 1번 과정에서 두개를 합친 수들을 sum배열에 담아놨기 때문에 x+y는 계산을 이미 완료했고 k-z가 sum배열에 존재하면 조건에 성립한다. 찾으면 바로 리턴해버리는 이유는 뒤쪽에서부터 찾기 때문에 제일 먼저 찾는 수가 최대값이기 때문이다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> input;
vector<int> sum;

bool binarySearch(int tar) {
    int start = 0;
    int end = sum.size() - 1;

    while(start < end) {
        int mid = (start + end) / 2;

        if(sum[mid] == tar) {
            return true;
        }

        if(sum[mid] < tar) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            sum.push_back(input[i] + input[j]);
        }
    }

    sort(input.begin(), input.end());
    sort(sum.begin(), sum.end());

    for(int i = n-1; i >= 0; i--) {
        for(int j = i; j >= 0; j--) {
            int a = input[i] - input[j];

            //bool check = binary_search(sum.begin(), sum.end(), a);
            bool check = binarySearch(a);
            if (check) {
                cout << input[i];
                return 0;
            }
        }
    }
}

---

3. Feedback

처음에 문제를 보자마자 우선순위 큐가 생각이 났다. 우선순위 큐로도 풀 수 있을 것같은데 한번 시도해 봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐