[백준 1448] 삼각형 만들기

문제출처: https://www.acmicpc.net/problem/1448

풀이

https://jow1025.tistory.com/35에도 나와있듯이, 삼각형의 성립조건은 세 변 a,b,c중 c가 가장 큰 변일 때 a+b>c일때입니다.

a+b>c일때 a,b,c의 합의 최댓값은 빨대의길이를 정렬하고 뒤에서부터(큰값부터)비교하면 됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int straw[1000001];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> straw[i];
	sort(straw + 1, straw + n + 1);
	//c가 가장 큰 변일 떄 a+b>c일떄 삼각형성립
	for (int i = n; i >= 2; i--)
	{
		int c = straw[i];
		int a = straw[i - 1];
		int b = straw[i - 2];
		if (a + b > c)
		{
			cout << a + b + c << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
}

결과