백준 2295 - 세 수의 합

문제 설명

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 수들 중 세 개를 골라 모두 더했을 때 그 결과가 주어진 수들 중에 있는지 구하면 된다.

그러한 수들중 가장 큰 결과를 선택하면 된다.

 

이를 간단하게 생각해 보면 세 개의 수를 고르고 합이 주어진 수 중 있는지 확인하면 된다.

이 과정은 $O(N^4)$이다.

N은 최대 1000이기 때문에 1초 안에 해결하는 것은 불가능하다.

그렇다면, 마지막 과정인 합을 찾는 과정을 이진 탐색을 적용한다면  $O(N^3logN)$만에 구할 수 있다.

하지만, 이 경우도 시간초과가 걸릴 것이다.

그럼 세 개의 수를 고르는 과정을 줄여야 할 것이다.

이는 간단한 트릭으로 해결할 수 있다.

두 개의 수의 합을 모두 구해놓은 상태로 나머지 두 수(합을 포함한)를 살펴보며 구해놓은 합들 중에 있는지 찾으면 된다.

즉, a + b + c = d라고 했을 때, a+b를 모두 구해놓는다면 d - c가 a+b 중에 있는지 찾으면 된다.

이때, a+b를 찾는 과정을 이진 탐색으로 처리하면 된다.

 

한 가지 유의할 점은 a, b, c, d가 모두 같을 수 있다는 조건이다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<int> nums;
vector<int> sum;

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N;
    
    nums.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> nums[i];
    }

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

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

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

    for (int i = N - 1; i >= 0; i--)
    {
        for (int j = i; j >= 0; j--)
        {
            int num = nums[i] - nums[j];
            if (binary_search(sum.begin(), sum.end(), num))
            {
                cout << nums[i];
                return 0;
            }
        }
    }

    return 0;
}

---