백준 : 2295번 세 수의 합(c++)

백준 링크

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

2295번: 세 수의 합

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	9115	2702	1821	28.813%

문제

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

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

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

예제 입력 1 복사

5
2
3
5
10
18

예제 출력 1 복사

18

코드 풀이

• N과 각 숫자의 입력값 할당
• vecNumb를 정렬
• vecNumb[x] + vecNumb[y]를 더해 vecTwo에 저장 (vecTwo를 만드는 이유는 시간 복잡도를 줄이기 위함)
• 이분탐색을 하기위한 vecTwo 정렬
• vecNumb[k] - vecNumb[z]값 vecTwo 이분탐색 진행

결국 O(N^2) 시간복잡도를 활용해 x + y를 하여 새로운 벡터(vecTwo)에 미리 저장을 한다

vecTwo + z를 하면 최종 k값이 나오기 때문에 이걸 반대로 생각하면 k - z = vecTwo가 되는 것을 알 수 있다.

그러므로 k - z를 한 값이 vecTwo에 있는 값인지 판별만 하면 되는 문제이다.

최종 시간복잡도 O(N^2logN)가 된다

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;

vector<int> vecNumber;
vector<int> vecTwoAdd;

void InputFunc()
{
    cin >> N;
    vecNumber.resize(N);

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

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

    InputFunc();

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

    for (int x = 0; x < N; ++x)
    {
        for (int y = x; y < N; ++y)
        {
            vecTwoAdd.push_back(vecNumber[x] + vecNumber[y]);
        }
    }

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

    for (int k = vecNumber.size() - 1; k >= 0; --k)
    {
        for (int z = 0; z < N; ++z)
        {
            if (binary_search(vecTwoAdd.begin(), vecTwoAdd.end(), vecNumber[k] - vecNumber[z]))
            {
                cout << vecNumber[k];
                return 0;
            }
        }
    }

    return 0;
}

---

이번 문제는 저 또한 시간복잡도 제한의 어려움이 있어 바킹독님의 풀이를 참고하여 풀었습니다.

https://www.youtube.com/watch?v=3TkaOKHxHnI&t=1360s