[백준] 2295 세 수의 합 - C++

 이 2295번 문제에 가장 간단하게 접근하는 방법은 arr[i] + arr[j] + arr[k] = arr[m] 방식으로 시간복잡도가 O(N^4)인 방법이 있을테고, arr[m]을 찾는 방식을 이분탐색으로 바꿔주면, O(N^3 * logN) 이 될 것이다. 이 문제가 정답율이 낮은 이유도 이렇게 다들 생각을 많이 하고 제출했더니 메모리 초과가 나거나 시간초과가 난 것 같다. 

 

 O(N^3 * logN) 코드는 다음과 같다. 이렇게 풀면 틀립니다

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N;
int arr[1005];
vector<int> three;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = j; k < N; k++) {
                three.push_back(arr[i] + arr[j] + arr[k]);
            }
        }
    }
    sort(three.begin(), three.end());

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (binary_search(three.begin(), three.end(), arr[i])) {
            ans = max(ans, arr[i]);
        }
    }
    cout << ans;
}

 

 하지만, 이보다 더 좋은 방법이 있다. 식을 조금 변형해서 arr[i] + arr[j] = arr[m] - arr[k] 로 해서 arr[i] + arr[j]를 two라는 벡터 변수에 저장해둔 뒤, arr[m] - arr[k]가 two 벡터에 있는지 이분탐색으로 탐색하면 시간 복잡도는 O(N^2 * logN)이 될 것이다. 이 방법을 알아내기만 하면 문제는 간단해진다.

 정답코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N;
int arr[1005];
vector<int> two;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            two.push_back(arr[i] + arr[j]);
        }
    }
    sort(two.begin(), two.end());

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