[C++] 백준 1448번:삼각형 만들기

문제링크

1448번: 삼각형 만들기

문제

세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다.

입력

첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 작거나 같다.

출력

첫째 줄에 삼각형 세 변의 길이의 합의 최댓값을 출력한다. 만약 삼각형을 만들 수 없으면 -1을 출력한다.

 

풀이

삼각형을 만들 수 있는 조건은 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작을 때 이다.

입력 받은 빨대를 길이가 긴 순으로 재정렬 시켜주고 가장 긴 변의 길이가 그 다음으로 긴 두 변의 길이의 합보다 작은지 판단하여 출력해주도록 한다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
 
bool compLenght(int a, int b) {
    if (a > b)return true;
    return false;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int> v(n);
 
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
 
    // 길이가 긴순으로 정렬
    sort(v.begin(), v.end(), compLenght);
 
    // 삼각형을 만들 수 있는지에 대한 flag
    bool possible = false;
    // 가장 긴 변의 index
    int maxIndex = 0;
 
    // 두 변의 길이가 가장 긴 변보다 길다면 가능
    for (int i = 0; i < n - 2; i++) {
        if (v[i] < v[i + 1] + v[i + 2]) {
            maxIndex = i;
            possible = true;
            break;
        }
    }
 
    if (possible == false) {
        cout << -1;
        return 0;
    }
 
    cout << v[maxIndex] + v[maxIndex + 1] + v[maxIndex + 2];
}

 

메모