C++로 배열의 원소로 삼각형을 만들 수 있는지 확인하는 방법

문제 개요

정수로 이루어진 배열이 주어졌을 때, 배열의 원소들을 삼각형의 세 변으로 사용하여 넓이가 0보다 큰(퇴화되지 않는) 삼각형을 만들 수 있는지 확인하는 문제입니다.

퇴화되지 않는 삼각형의 조건

퇴화되지 않는(non-degenerate) 삼각형이란 양수의 넓이를 가지는 삼각형을 의미합니다. 세 변의 길이가 a, b, c일 때 다음 세 가지 부등식을 모두 만족해야 합니다.

a + b > c
a + c > b
b + c > a

예제를 통해 문제를 더 자세히 살펴보겠습니다.

입력 − arr[] = {2, 5, 9, 4, 3}

출력 − Yes

설명 − 2, 3, 4를 변으로 하는 삼각형을 만들 수 있습니다.

해결 접근 방법

배열의 값들이 위 조건을 만족하는지 확인하면 됩니다.

단순한 방법 − 배열에서 가능한 모든 세 원소 조합(트리플릿)을 하나씩 직접 검사하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(N³)으로 매우 비효율적입니다.

효율적인 방법 − 먼저 배열을 오름차순으로 정렬한 뒤, 연속된 세 원소씩만 검사하는 것입니다. 정렬된 배열에서는 arr[i] + arr[i+1] > arr[i+2] 조건만 확인하면 충분합니다. 두 짧은 변의 합이 가장 긴 변보다 커야 한다는 조건이 가장 까다롭기 때문에, 나머지 두 부등식은 자동으로 성립합니다. 또한 연속된 세 원소에서 조건이 실패하면 그 이후의 값들은 이미 더 크기 때문에 더 이상 검사할 필요가 없습니다.

C++ 구현 예제

위 해결 방법을 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
bool isTrianglePossible(int arr[], int N){
    if (N < 3)
        return false;
    sort(arr, arr + N);
    for (int i = 0; i < N - 2; i++)
        if (arr[i] + arr[i + 1] > arr[i + 2])
            return true;
}
int main() {
    int arr[] = {5, 12, 13, 65, 6, 1};
    int N = sizeof(arr) / sizeof(int);
    cout<<"배열의 원소로 삼각형 생성 ";
    isTrianglePossible(arr, N)?cout<<"가능함": cout<<"불가능함";
    return 0;
}

출력 결과

배열의 원소로 삼각형 생성 가능함

시간 복잡도 분석

배열 정렬에 O(N log N)의 시간이 소요되고, 이후 연속된 세 원소를 순회하는 과정은 O(N)이므로 전체 시간 복잡도는 O(N log N)입니다. 모든 조합을 검사하는 단순한 방법(O(N³))에 비해 훨씬 효율적입니다.