[백준] 2295번 세 수의 합

문제: 2295번: 세 수의 합

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

bool binarySearch(int target, vector<int>& set) {
    int st = 0;
    int en = set.size();

    while (st < en) {
        int mid = (st + en) / 2;

        if (set[mid] == target)
            return true; // 찾았으니까 true 반환행~
        else if (set[mid] < target)
            st = mid + 1;
        else
            en = mid - 1;
    }
    // 여기까지 온거면 target 이 존재하지 않는거임
    return false;
}

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

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

    // 이 set 에 있는 요소 두개씩 묶어서 새로운 집합 만들엉
    vector<int> twoSet;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            twoSet.push_back(set[i] + set[j]);
        }
    }
    sort(twoSet.begin(), twoSet.end());
   
    int max = -1;
    // 이제 twoSet 에 a[l] - a[k] 가 존재하는지 이분탐색 할거임
    for (int i = 0; i < n; i++) {
        // 일단 set[l] 이 세수의 합인 가능성이 있는 거자너~
        for (int j = 0; j < n; j++) {
            // 일단 set 에서 set[k] 지정해야하자너!
            // set[l] - sets[k] 값이 two 에 존재하는지 이분탐색으로 확인행~

            int target = set[i] - set[j];
            if (binarySearch(target, twoSet)) {
                if (max < set[i])
                    max = set[i];
            }
        }
    }
    cout << max;
    
    return 0;
}

 

아!!!!!!!!!!!!!!! 한 번에 풀 수 있었는데 어이없는 실수를 해서 틀렸다.. 이분탐색인데 왜 정렬을 안 하고 탐색 돌렸는지;;;

 

아무튼 이 문제를 해결하기 위해서는 O(N^2lgN) 의 시간복잡도 풀이가 필요하다. 이와같은 시간복잡도를 얻기 위해서는 일단 twoSet 배열을 새로 만들어주는 방법이 있다.

 

twoSet 배열을 만든다는 의미는 기존의 set 배열에 존재하는 요소들을 두개씩 짝지어서 더한다는 것이다. 만약 set 의 요소가 1, 4, 6 이었다면 twoSet 의 요소는 {1+1, 1+4, 1+6, 4+4, 4+6, 6+6} 이다. 자기 자신과 같이 더할 수 있는 이유는 문제에서 중복해서 더하는게 가능하다고 말했기 때문...

 

아무튼 이렇게 twoSet 을 새로 만들어주면 이제 이분탐색 돌리면 된다. a[i]+a[j]+a[k] = a[l] 의 식을 twoSet 을 이용하면 two[m] + a[k] = a[l] 가 된다. 이 식을 이용하면 a[l] - a[k] 의 값이 twoSet 에 존재하는지 여부를 판단하는 식으로 문제를 해결할 수 있다.

 

a[l] - a[k] 의 값이 twoSet 에 존재하는지 여부는 이분탐색을 돌리면 된다. 이분탐색 돌리기 전에 twoSet 을 오름차순으로 정렬하고 했어야 했는데 나는 이걸 깜빡해서 그만...;;

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x13강 - 이분탐색