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

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

문제

---

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

 

입력

---

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

 

출력

---

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

 

 

문제 풀이

---

그리디 문제.

 

삼각형의 어느 한 변의 길이가 a라면 나머지 두 변의 길이의 합은 a보다 크다.

따라서 정렬 후 가장 긴 빨대부터 삼각형의 가장 긴 변이라고 가정하고 나머지 두 변이 될 수 있는 길이가 있는지 찾는다. 우리가 찾는 것은 세 변의 길이의 합의 최댓값이므로 i번째 빨대를 가장 긴 변이라 가정한다면 i-1번째 빨대와 i-2번째 빨대의 합을 확인하면 된다. 이것이 최대가 되므로 이 두 합이 i번째 빨대보다 작거나 같다면 i번째 빨대가 가장 긴 변인 삼각형을 만들 수 없고, i번쨰 빨대보다 크다면 삼각형을 만들 수 있다. 최댓값을 찾는 문제이므로 반복문을 빠져나오면 된다.

 

아래는 코드.

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

int main()
{
	int N;
	bool canMake = false;
	cin >> N;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = N - 1; i >= 2; i--)
	{
		if (arr[i] < arr[i - 1] + arr[i - 2])
		{
			canMake = true;
			cout << arr[i] + arr[i - 1] + arr[i - 2];
			break;
		}
	}
	if (canMake == false)
	{
		cout << -1 << "\n";
	}
	return 0;
}