[백준] 1448번 - 삼각형 만들기 (C++) 문제 및 풀이

문제) 백준 - 그리디 (Greedy) - 삼각형 만들기

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

1448번: 삼각형 만들기

 

 

세 변으로 만들 수 있는 삼각형 중 세 변의 합의 최대를 구하는 문제. N이 100만이므로 O(nC3)으로 완전 탐색이 불가능한다. 최대만 구하면 되므로 모든 변을 내림차순으로 정렬한 뒤, 삼각형을 이룰 수 있는 변 3개가 존재하면 답을 출력한다.

 

 

 

C++ 소스코드)

 

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 1000001
	#define MOD 1000000000
	#define int ll
	using namespace std;
	int arr[MAX];
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
	cin >> arr[i];
	}
	sort(arr, arr + n);
	for (int i = n - 3; i >= 0; --i) {
	if (arr[i + 2] < arr[i + 1] + arr[i]) {
	cout << arr[i + 2] + arr[i] + arr[i + 1] << endl;
	break;
	}
	else if (i == 0) {
	cout << -1 << endl;
	}
	}
	return 0;
	}

view raw 1448.cpp hosted with ❤ by GitHub