백준 2295번 [세 수의 합](C++) -yes6686- 티스토리

백준 문제 풀이: 2295 (세 수의 합)

---

문제 링크: https://www.acmicpc.net/problem/2295

문제 설명:

주어진 수열에서 **세 수를 선택하여 합이 네 번째 수와 같은** 가장 큰 값을 구하는 문제입니다. 입력으로 주어진 수열의 각 원소는 **중복이 허용되며**, 합이 일치하는 경우가 여러 개 있을 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[1001];           // 입력 수열
vector<int> v;           // 두 수의 합을 저장하는 벡터

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 수열의 크기
    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 = 0; j < n; j++) {
            v.push_back(arr[i] + arr[j]);
        }
    }

    // 벡터를 정렬 (이분 탐색을 위해)
    sort(v.begin(), v.end());

    // 세 수의 합 중에서 최대값 찾기
    for (int i = n - 1; i >= 0; i--) { // 배열의 큰 수부터 탐색
        for (int j = 0; j <= i; j++) {
            int k = arr[i] - arr[j]; // 차이값 계산
            if (binary_search(v.begin(), v.end(), k)) { // 두 수의 합과 일치 여부 확인
                cout << arr[i] << '\n'; // 결과 출력
                return 0; // 가장 큰 값을 찾으면 종료
            }
        }
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 입력 수열 정렬: - 정렬을 통해 이분 탐색과 최적화를 수행할 수 있습니다.
• 두 수의 합 저장: - arr[i] + arr[j]를 벡터 v에 저장합니다.
• 이분 탐색 활용: - binary_search를 사용해 벡터 v에서 k 값을 찾습니다. 여기서 k = arr[i] - arr[j]입니다.
• 가장 큰 값부터 탐색: - 가장 큰 arr[i]부터 탐색하면 조건을 만족하는 **최대값**을 빠르게 찾을 수 있습니다.

시간 복잡도 분석

• 두 수의 합을 계산: **O(n²)**
• 벡터 정렬: **O((n²) log (n²)) ≈ O(n² log n)**
• 세 수 탐색 및 이분 탐색: **O(n² log n)**
• 총 시간 복잡도: **O(n² log n)**

---

결과

주어진 수열에서 세 수의 합이 네 번째 수와 같은 경우 중 **가장 큰 수**를 출력합니다.

• 입력 예시:

  4  
  2 3 5 10

• 출력 예시:

  10

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!