선분의 길이가 주어질때 볼록 다각형(conver polygon)이 될 조건

1. 문제

 

18044번: Polygon (acmicpc.net)

18044번: Polygon

 

2. 풀이

 

convex polygon은 앞으로 배울것 같지만...

 

지금은 모든 내각이 180도보다 작거나 같은 도형이라고 이해하면 될 것 같다

 

https://en.wikipedia.org/wiki/Convex_polygon

Convex polygon - Wikipedia

 

선분의 길이가 주어질때 최대 둘레를 가진 convex polygon을 만들도록 선분을 선택하라는게 문제인데.. 어떻게 해야할까?

 

삼각형 같은 경우 convex polygon일거고 여기서 아이디어를 얻어본다면 

 

"가장 긴 변의 길이가 나머지 두변의 길이 합보다 작다"여야 삼각형인데

 

일반적인 n각형이 convex polygon일려면,

 

"가장 긴 변의 길이가 나머지 변의 길이 합보다 작다"여야 할 것 같다.

 

찾아봐도 어디 증명은 없는것 같고

 

직관적으로 다음 그림이 미쳤다

 

 

나머지 변들의 길이를 하나씩 붙여서 일직선으로 만들때, 가장 긴변의 길이보다 커야 위의 도형이 나오고

 

가장 긴변의 길이보다 작다면 아래 도형이 나오게 되는...

 

------------------------------------------------------------------------------------------------------------------------------------------

 

조건을 알긴 했지만 단순하게 문제에 접근하면 시간 초과 가능성이 높은게 

 

테스트 케이스는 10만개인데 각 케이스마다 n의 수가 최대 10만개라 단순하게는 1초안에 모두 답하기 쉽지 않을 것 같다

 

결국 최대 둘레의 길이를 찾으면 되니까, 일단 모든 변의 길이를 전부 합한다

 

그리고 변의 길이를 오름차순 정렬

 

그러면 현재 순간 최댓값은 마지막 원소니까 n-1부터 0까지 순회를 한다

 

(모든 변의 길이 합) - (최대 변의 길이)와 (최대 변의 길이)를 비교

 

최대 변의 길이가 더 크다면, (모든 변의 길이 합) = (모든 변의 길이 합) - (최대 변의 길이)로 갱신하고, 다음으로 진행

 

하지만 최대 변의 길이가 더 작다면? 여기서 끝내면, 그게 둘레의 최댓값이 된다

 

또한 당연하지만 일각형 이각형 이런건 없잖아... n이 3보다 작으면 바로 0을 print

 

#convex polygon이 될 조건
#"가장 긴 변의 길이가 나머지 변의 길이 합보다 작다"
from sys import stdin

z = int(stdin.readline())

for _ in range(z):
    
    n = int(stdin.readline())

    lines = list(map(int,stdin.readline().split()))

    if n < 3:
        
        print(0)
    
    else:

        lines.sort()

        remainder = sum(lines)

        for i in range(n-1,-1,-1):
            
            #최대 < (모든 변 길이합) - 최대이면 바로 break
            #최대 >= (모든 변 길이 합) - 최대 이면, 현재 최대 변은 선택 불가능
            if lines[i] >= remainder - lines[i]:
                
                remainder -= lines[i]
            
            else:
                
                break
        
        print(remainder)