삼각형 만들기 C++ - 백준 1448

https://www.acmicpc.net/problem/1448

이 문제는 그리디를 써서 푸는 문제이다.

일단 변의 길이 배열을 비오름차순 정렬하고 변 길이의 합의 최댓값을 찾아야

하기 때문에 최대값부터 탐색한다.

arr[i]를 최댓값이라고 하면 arr[i+1] + arr[i+2]보다 크면

arr[i]를 변으로 하는 삼각형은 존재하지 않기(이보다 큰수가 나올 수

없기 때문이다.) 때문에 다음 arr[i]를 탐색하는 식으로

알고리즘을 작성했다.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[1000000];
bool flag=false;
int ans;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	sort(arr,arr+n,[](int l, int r)->bool{return l>r;});
	for(int i=0;i<n-2;i++){
		if(arr[i]<arr[i+1]+arr[i+2]){
			ans=arr[i]+arr[i+1]+arr[i+2];
			break;
		}
	}
	if(ans!=0) cout << ans;
	else cout << -1;
}