[백준 1448번] 삼각형 만들기 풀이

1448번: 삼각형 만들기

 

빨대 N개의 길이를 벡터 v에 저장하였을 때, 세가지 빨대의 조합으로 삼각형을 만들 수 있는지 확인하는 가장 간단한 방법은,  삼중 for문을 돌면서 세가지 빨대의 조합을 찾고, 해당 조합이 삼각형의 조건을 만족하는지 찾으면 된다. 그러나, 해당 알고리즘의 시간 복잡도는 O(N^3)이므로 시간 초과가 날 가능성이 매우 높다.

 

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++) {
            
            // v[i], v[j], v[k] 조합으로 삼각형의 조건을 만족할 수 있는지 확인
            
        }	
    }
}

 

따라서 우리는 다른 방식으로 문제에 접근해야 한다.

먼저, 세변의 길이가 삼각형을 만족하기 위해서는 가장 긴 변(a)의 길이가 나머지변(b, c) 길이의 합보다 작아야 한다. (a < b+c) 입력된 빨대의 길이들을 벡터 v에 저장하고, 이를 내림차순으로 정렬하면 벡터의 가장 왼쪽에 가장 긴 변의 길이가, 가장 오른쪽에 가장 짧은 변의 길이가 저장된다. 

 

예를 들어, 빨대의 길이가 4 6 5 7 20으로 입력되었을 때 이를 내림차순으로 정렬하면 v = { 20 7 6 5 4 } 이다. 

v[0](20)을 가장 긴 변(a) 라 가정하자. 이 때 i+1 부터 저장되어있는 원소들은 모두 20보다 작은 값이므로 나머지 변들의 후보가 될 수 있다.

 

만약 v[0] < v[1]+v[2] 라면 가장 긴 변의 길이가 나머지 두 변의 합보다 짧은 것이므로 삼각형을 만족한다.

만약 v[0] < v[1]+v[2] 를 만족하지 않는다면, 그 뒤는 더 볼 것도 없이 v[0]는 가장 긴 변이 되지 못한다. v[0]를 제외한 값들 중 가장 큰 값은 v[1]과 v[2]이기 때문에 v[2]+v[3], v[3]+v[4] 와 같은 값들은 당연히 v[0]보다 클 수 없다. 

 

이렇게 i를 0부터 N-3까지 순회시키면서 v[i]를 가장 긴변으로 가정하고, v[i] < v[i+1]+v[i+2] 를 만족하는지 확인한다. 조건을 만족시키는 v[i], v[i+1], v[i+2]를 찾았을 때, 현재 시점에서 삼각형을 만들 수 있는 가장 긴 변들의 값이 되므로 세 변의 합을 구해 바로 출력하면 최댓값이 된다. 

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

int main() {

    int N;
    scanf("%d", &N);

    vector<int> v(N);
    for (int i=0; i<N; i++) 
        scanf("%d", &v[i]);
    
    sort(v.begin(), v.end(), greater<>());
    for (int i=0; i<N-2; i++) {
        if (v[i+1]+v[i+2] > v[i]) {
            printf("%d\n", v[i]+v[i+1]+v[i+2]);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}