문제 설명
음수가 아닌 정수로 이루어진 배열이 주어졌을 때, 이 배열의 원소 중 세 개를 선택하여 만들 수 있는 삼각형 중 둘레(세 변의 길이의 합)가 가장 큰 삼각형을 찾는 것이 목표입니다.
여기서 중요한 점은 임의의 세 수가 모두 삼각형을 이루는 것은 아니라는 것입니다. 삼각형이 성립하려면 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작아야 한다는 조건을 만족해야 합니다.
예시
입력 배열이 {5, 1, 3, 5, 7, 4}라면 최대 둘레는 (7 + 5 + 5) = 17 입니다.
알고리즘
- 배열을 내림차순(비증가 순서)으로 정렬합니다. 그러면 첫 번째 원소가 가장 크고, 마지막 원소가 가장 작아집니다.
- 정렬된 배열에서 왼쪽부터 연속된 세 원소(arr[i], arr[i+1], arr[i+2])를 검사합니다.
arr[i] < arr[i+1] + arr[i+2]조건을 처음 만족하는 순간, 그 세 원소가 바로 최대 둘레를 가지는 삼각형입니다. 즉시 결과를 반환하면 됩니다.
이 방법이 동작하는 이유
내림차순으로 정렬된 상태에서는 앞쪽에 있는 값일수록 큽니다. 따라서 어떤 위치 i에서 삼각형 조건이 성립하지 않는다면(arr[i] ≥ arr[i+1] + arr[i+2]), i보다 뒤의 원소들을 사용하는 조합 역시 두 짧은 변의 합이 더 작아지므로 삼각형을 만들 수 없습니다. 반대로 조건을 처음 만족하는 시점의 세 원소는 가능한 조합 중 가장 큰 값들로 구성되어 있으므로 둘레가 최대가 됩니다. 이러한 탐욕적(greedy) 접근 덕분에 전체 시간 복잡도는 정렬에 의해 지배되는 O(n log n)으로 매우 효율적입니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMaxPerimeter(int *arr, int n) {
// 내림차순 정렬
sort(arr, arr + n, greater<int>());
int maxPerimeter = 0;
for (int i = 0; i < n - 2; ++i) {
// 삼각형 성립 조건 검사
if (arr[i] < arr[i + 1] + arr[i + 2]) {
maxPerimeter = max(maxPerimeter,
arr[i] + arr[i+1] + arr[i+2]);
break;
}
}
if (maxPerimeter) {
return maxPerimeter;
}
return -1;
}
int main() {
int arr[] = {5, 1, 3, 5, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int maxPerimeter;
maxPerimeter = getMaxPerimeter(arr, n);
if (maxPerimeter != -1) {
cout << "Max perimeter = " << maxPerimeter <<
endl;
} else {
cout << "Triangle formation is not possible" <<
endl;
}
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Max perimeter = 17
배열 {5, 1, 3, 5, 7, 4}를 내림차순으로 정렬하면 {7, 5, 5, 4, 3, 1}이 되고, 처음 세 원소인 7, 5, 5는 7 < 5 + 5 조건을 만족하므로 최대 둘레는 7 + 5 + 5 = 17이 됩니다. 만약 어떤 조합으로도 삼각형을 만들 수 없다면 프로그램은 -1을 반환하여 "삼각형 생성 불가" 메시지를 출력합니다.