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

문제링크 ; https://www.acmicpc.net/problem/1448

1448번: 삼각형 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, arr[1000001];
int result = -1;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++) cin >> arr[i];

    sort(arr, arr + N);

    for(int i=N-1; i>1; i--) //뒤에서부터
    {
        if(arr[i] < arr[i-1] + arr[i-2]) //삼각형 조건
        {
            result = arr[i] + arr[i-1] + arr[i-2];
            break;
        }
    }
    cout << result;

    return 0;
}

 

삼각형의 조건은 두 변의 길이의 합이 나머지 한 변의 길이보다 커야하는 것이다.

문제에서 가장 큰 변의 합을 원하므로, 입력받은 값을 정렬해준 뒤 가장 큰 값에 해당하는 뒤쪽부터 해당 조건을 살펴본다.

만약 조건을 부합하는 값이 있다면 가장 큰 값에 해당하므로 바로 종료시키고 출력한다.