[BOJ 1448] 삼각형 만들기

$N$개의 길이 중 3개를 선택하여 삼각형을 만들었을 때, 세 변의 길이의 합의 최댓값을 구하는 문제이다. 

 

그리디하게 접근해 보자. 세 변의 길이의 합을 최대로 만들려면 당연히 길이들 중 최대한 긴 것을 선택해야 한다. 그렇다면 정렬을 먼저 해보자. 

 

가장 큰 3개를 봤을 때, 삼각형이 안 되면 어떤 길이를 선택해야 할까?

 

XXXXXXXOOO에서 XXXXXXOXOO 이런 식으로 선택을 해야 할까? 

 

삼각형을 이루는 세 변의 길이의 조건을 생각해 보자.

'가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 한다.'

 

가장 긴 3개를 골랐을 때, 삼각형이 안 된다면 가장 긴 길이를 유지한 채로 다른 변을 더 짧은 길이를 선택하는 것은 삼각형에서 멀어지는 길이다. 위의 상황과 같이 가장 긴 길이를 기준으로 바로 다음 2개의 변으로 삼각형을 만들지 못한다면, 해당하는 가장 긴 길이의 변으로는 삼각형을 만들지 못한다.

 

즉, 연속되는 3개의 변만 차례로 확인하면 된다.

int N; 
vector<int> v;

int main(void) {
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        v.push_back(x);        
    }
    sort(all(v), greater<int>());

    for (int i = 0; i < N - 2; i++) {
        if (v[i] < v[i + 1] + v[i + 2]) {
            cout << v[i] + v[i + 1] + v[i + 2] << "\n";
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}