※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
삼각형이 성립하려면 어느 두 변의 합이 나머지 변의 합보다 항상 커야 합니다. 그 조건을 만족하는 조건을 찾기 위해서 얼마나 많은 조합을 테스트 해봐야 할까요?
$n$의 제한이 1,000,000 이므로 $O(n^3)$ 의 복잡도로 풀 수 없습니다. 하지만 잘 생각해보면 모든 경우를 다 테스트 해 보지 않아도 삼각형을 최대로 만드는 경우를 찾을 수 있습니다. 만약 어느 변 a,b,c를 골랐을 때 삼각형이 되지 않는다면, 이 중 가장 긴 변을 제외하고, 나머지 1변을 추가하여 테스트 해보는 방식으로 조건에 맞는 삼각형을 찾으면 되는 것을 알 수 있습니다.
즉, 삼각형을 변의 길이로 정렬 후, 가장 긴 3개부터 시작하여 삼각형이 성립하는지를 확인하며, 성립하지 않을 경우 가장 긴 변을 버리고 다음 변을 가져와 확인하면 $O(nlogn)$의 시간복잡도로 해결할 수 있습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int w[1000001];
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i];
sort(w, w + n);
for (int i = n - 3; i >= 0; i--)
{
int a = w[i], b = w[i + 1], c = w[i + 2];
if (a + b > c && a + c > b && b + c > a)
{
return cout << a + b + c, 0;
}
}
cout << -1;
}