백준 g4 2295 세 수의 합 c++

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

2295번: 세 수의 합

 

문제

N개의 수로 이루어진 집합 U가 있을 때, 

각 원소 a, b, c, k를 골랐을 때 a + b + c = k 를 만족하는 최대 k 구하기

 

집합이므로 각 원소는 중복되지 않으나, a b c 는 서로 같아도 된다.

 

풀이

1. O(N^3*logN) 풀이

1) 세 원소를 고른다. 1000C3 -> N^3

2) 고른 세 원소의 합이 존재하는지 binary_search -> logN

 

그러나 N <= 10^3 으로 아마 시간초과가 뜰 듯 ... 

 

2. O(N^2l*logN) 풀이(https://blog.encrypted.gg/985)

1) 원본 배열에서 두 개의 합을 더해놓은 two 배열을 구함. -> N^2

2) two[i] + a[j] = a[k] ( == a[k] - a[j] = two[i])를 만족하는 a[k]를 구함.

    이때 for i, j 로 하면 시간복잡도가 N^3이 되어버리므로 for j, k로 해야 함.

 

수도 코드

//1. two 배열 구하기
for i, j: 0 ~ N
	two.push(a[i] + a[j])
   
 //2. two[i] + a[j] = a[k]를 만족하는 a[k] 구하기
 // == a[k] - a[j] = two[i]를 만족하는
 for j, k: 0 ~ N
 	if binary_search(a[k] - a[j], two[i])
    	ans = max(ans, a[k]

 

코드

/*boj g4 2295 세 수의 합*/
#include <algorithm>
#include <iostream>
#include <vector>
#define MAXN 1010
using namespace std;

int N;
vector<int> two;
int a[MAXN];
int ans = -99;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    // 1. two 배열 만들기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            two.push_back(a[i] + a[j]);
        }
    }

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

    // 2. two[i] + a[j] = a[k] 일 때, two[i]가 존재하는 지 확인
    for (int k = 0; k < N; k++) {
        for (int j = 0; j < N; j++) {
            if (binary_search(two.begin(), two.end(), a[k] - a[j])) {
                ans = max(ans, a[k]);
            }
        }
    }

    cout << ans << "\n";
}