# [Gold I] 수집합 [문제 링크](https://www.acmicpc.net/problem/4373) ## 문제 설명 <p>정수 집합 S가 주어졌을 때, a + b + c = d를 만족하는 가장 큰 d를 구하는 프로그램을 작성하시오. 이때, a, b, c, d는 S의 원소이며, 서로 다른 수이다.</p> ## 입력 <p>입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 집합 S의 크기 n(1 ≤ n ≤ 1000)이 주어진다. 다음 줄부터 n개의 줄에는 집합 S의 원소(-536870912 ~ +536870911)가 하나씩 주어진다. 집합의 원소는 중복되지 않는다. 입력의 마지막 줄에는 0이 주어진다.</p> ## 출력 <p>각 테스트 케이스에 대해서, 가장 큰 d를 출력한다. d가 없는 경우에는 "no solution"을 출력한다.</p> ## 풀이 * a+b = d-c로 식을 변형시킨 후, a+b의 경우의 수와 d-c, c-d의 경우의 수를 전부 벡터에 담는다. (MITM) * 값을 기준으로 오름차순으로 정렬한다. * 투 포인터 시작 * 두 포인터를 전부 0에서 시작해서 a+b < d-c인 경우 a+b 포인터 오른쪽으로 이동. * a+b = d-c이고 모든 수가 다른 경우 최댓값 기록하고 d-c 포인터를 오른쪽으로 이동. * 그렇지 않은 경우 d-c 포인터를 오른쪽으로 이동. * 오른쪽으로 이동시키는 이유는 d-c에서 5-3은 5가 저장되고 6-4는 6이 저장되서 합이 같더라도 끝까지 살펴봐야 한다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); while(true) { int n; cin >> n; if(!n) break; vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i]; vector<vector<int>> aPlusB, dMinusC; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { aPlusB.push_back({v[i]+v[j], v[i], v[j]}); dMinusC.push_back({v[i]-v[j], v[i], v[j]}); dMinusC.push_back({v[j]-v[i], v[j], v[i]}); } } sort(aPlusB.begin(), aPlusB.end()); sort(dMinusC.begin(), dMinusC.end()); int maxVal=INT_MIN, l=0, r=0; while(l<aPlusB.size() && r<dMinusC.size()) { if(aPlusB[l][0]==dMinusC[r][0] && aPlusB[l][1]!=dMinusC[r][1] && aPlusB[l][1]!=dMinusC[r][2] && aPlusB[l][2]!=dMinusC[r][1] && aPlusB[l][2]!=dMinusC[r][2]) { maxVal = max(maxVal, dMinusC[r][1]); r++; } else if(aPlusB[l][0]<dMinusC[r][0]) l++; else r++; } cout << (maxVal==INT_MIN ? "no solution" : to_string(maxVal)) << '\n'; } } ```