백준 2295 - 세 수의 합 (C++)

문제

• 문제 링크

  
   BOJ 2295 - 세 수의 합 
  

• 문제 요약

$N$개의 자연수로 이루어진 집합 $U$가 주어진다.
적당한 세 수를 골라 더하여 집합 내 수를 표현할 때, 표현할 수 있는 가장 큰 수를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$5 ≤ N ≤ 1,000$

$1 ≤ N_i ≤ 200,000,000$

답이 항상 존재함이 보장된다.

알고리즘 분류

• 자료 구조(data strucutures)
• 해시를 사용한 집합과 맵(hash _ set / map)
• 중간에서 만나기(meet in the middle)

풀이

$w$가 $U$에 속할 때, $x + y + z = w$를 만족하는 가장 큰 $(x, y, z)$를 찾아야 한다.

삼 중 포문으로 $TLE$ 맞기 딱 좋은 발상이 떠오를 수 있지만, 주어진 식을 $x + y = w - z$ 로 놓고 보면 쉬워진다.
수열이 단조 증가 하도록 정렬을 하고, 가능한 $(x, y)$ 쌍을 집합에 추가함과 동시에 $x - y$ 의 값이 집합에 존재하는지 검사하자.

그럼 단순히 이 중 포문으로도 쉽게 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
unordered_set <int> S;
int n, r, a[1001];
 
int main()
{
    cin >> n;
    for (int i{}; i < n; scanf("%d", &a[i++]));
    sort(a, a + n);
    for (int i{}; i < n; i++)
        for (int j{}; j <= i; j++)
            if (S.insert(a[i] + a[j]); S.count(a[i] - a[j]))
                r = max(r, a[i]);
    cout << r;
}

comment

끝