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

🎨 문제

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

• 알고리즘 분류: 수학, 그리디 알고리즘, 정렬
• 난이도: Silver 3

 

💬 풀이

세 변이 a,b,c인 삼각형에서 c가 가장 긴 변일 때 삼각형이 결정되는 조건은 c < a+b 다.

 

가능한 경우 중 최대를 구하면 되므로 입력받은 배열을 정렬해준 다음, 차례대로 위 삼각형 성립 조건이 되면 출력하고 종료하면 된다.

내림차순 정렬을 위해선 sort()와 greater<>()를 이용했다.

 

 

 

👩‍💻 코드

C++

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

bool isTriangle(int c, int a, int b) {
	if (c < a + b) { return true; }
	else { return false; }
}

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;
	int* input = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> input[i];
	}

	sort(input, input + N, greater<int>());

	for (int i = 0; i < N-2; i++) {
		int c, a, b;
		c = input[i];
		a = input[i + 1];
		b = input[i + 2];
		if (isTriangle(c, a, b)) {
			cout << c + a + b;
			return 0;
		}
	}
	cout << -1;

	delete[] input;
	return 0;
}