삼각형 만들기


작성일 : 2017-01-18 21:54:16
조회수 : 663



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


삼각형이 성립하려면 어느 두 변의 합이 나머지 변의 합보다 항상 커야 합니다. 그 조건을 만족하는 조건을 찾기 위해서 얼마나 많은 조합을 테스트 해봐야 할까요?


$n$의 제한이 1,000,000 이므로 $O(n^3)$ 의 복잡도로 풀 수 없습니다. 하지만 잘 생각해보면 모든 경우를 다 테스트 해 보지 않아도 삼각형을 최대로 만드는 경우를 찾을 수 있습니다. 만약 어느 변 a,b,c를 골랐을 때 삼각형이 되지 않는다면, 이 중 가장 긴 변을 제외하고, 나머지 1변을 추가하여 테스트 해보는 방식으로 조건에 맞는 삼각형을 찾으면 되는 것을 알 수 있습니다.


즉, 삼각형을 변의 길이로 정렬 후, 가장 긴 3개부터 시작하여 삼각형이 성립하는지를 확인하며, 성립하지 않을 경우 가장 긴 변을 버리고 다음 변을 가져와 확인하면 $O(nlogn)$의 시간복잡도로 해결할 수 있습니다.

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int w[1000001];
int main()
{
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];
    sort(w, w + n);

    for (int i = n - 3; i >= 0; i--)
    {
        int a = w[i], b = w[i + 1], c = w[i + 2];
        if (a + b > c && a + c > b && b + c > a)
        {
            return cout << a + b + c, 0;
        }
    }
    cout << -1;
}

삼각형 만들기 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글