백준 1448번: 삼각형 만들기

 

풀이

 삼각형이 만들어 질 수 있는 세 변의 길이는 a < b + c이다. 즉, 선택한 3개의 빨대 길이 중 최대값이 나머지 두 빨대 길이의 합보다 작아야 한다. 그래서 입력값을 벡터에 저장한 다음 오름차순으로 정렬하고, 벡터의 가장 마지막 요소부터 3개의 빨대 길이를 골라 a < b + c를 충족하는지 확인해주었다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
}

int N, a, b, c;
vector<int> v;
bool possible = false;

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int input;
		cin >> input;
		v.push_back(input);
	}

	sort(v.begin(), v.end());

	for (int i = N - 2; i >= 1; i--) {
		a = v.at(i - 1); b = v.at(i); c = v.at(i + 1);
		if (c < a + b) {
			possible = true;
			break;
		}
	}

	if (possible) cout << a + b + c;
	else cout << "-1";

}