C++에서 만들 수 있는 삼각형의 개수 구하기

삼각형의 변 길이들이 담긴 배열이 주어졌을 때, 이 배열에서 임의의 세 변을 선택하여 만들 수 있는 삼각형의 개수를 구하는 것이 목표입니다.

세 변이 삼각형을 이루려면 두 변의 길이 합이 항상 나머지 한 변보다 커야 한다는 삼각 부등식 조건을 활용합니다. 어떤 세 변이 이 조건을 만족하면 해당 조합으로 삼각형을 만들 수 있으므로, 가능한 삼각형의 개수를 하나씩 늘려 가며 계산합니다.

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

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

출력 − 만들 수 있는 삼각형의 개수: 1

설명 − (2,4,5)만이 삼각형을 만들 수 있습니다. 2+4>5, 4+5>2, 2+5>4를 모두 만족하기 때문입니다.

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

출력 − 만들 수 있는 삼각형의 개수: 7

설명 − (4,5,6), (4,5,3), (4,5,2), (4,6,3), (4,3,2), (5,6,3), (5,6,2) 조합이 모두 삼각형을 만들 수 있습니다.

프로그램에서 사용된 접근 방식

양의 정수들로 초기화된 정수 배열 arr[]를 준비합니다.
countTriangles(int arr[], int n) 함수는 배열과 그 길이를 인자로 받아 만들 수 있는 삼각형의 개수를 반환합니다.
삼각형 개수(count)의 초기값은 0으로 설정합니다.
세 변을 각각 선택하기 위해 세 개의 중첩 for 루프를 사용합니다.
가장 바깥쪽 루프는 0<=i<n-2, 그다음 루프는 i<j<n-1, 가장 안쪽 루프는 j<k<n 범위로 반복합니다.
arr[i], arr[j], arr[k]가 삼각형의 세 변을 이루는지 확인합니다.
arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i] 조건이 참이면 count를 1 증가시킵니다.
모든 조합을 검사한 후 count를 결과로 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int countTriangles(int arr[], int n){
    // Count of triangles
    int count = 0;
    for (int i = 0; i < n-2; i++){
        for (int j = i + 1; j < n-1; j++){
            for (int k = j + 1; k < n; k++){
                //any two sides have sum > third
                if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i])
                    { count++; }
            }
        }
    }
    return count;
}
int main(){
    int Arr[] = { 1,2,5,3,6,8,10 };
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "count of Triangles possible : "<< countTriangles(Arr, len);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

count of Triangles possible : 8

복잡도 및 최적화 팁

위 방식은 세 변의 모든 조합을 검사하므로 시간 복잡도는 O(n³)입니다. 배열의 크기가 커지면 성능이 빠르게 저하될 수 있습니다.

배열을 먼저 오름차순으로 정렬하면 가장 큰 변(arr[k])만 확인하면 되므로, 내부 조건 검사를 단순화하여 시간 복잡도를 O(n²)까지 줄일 수 있습니다. 입력 데이터가 많은 경우 정렬 기반 최적화를 적용하는 것이 좋습니다.