백준 1448번 : 삼각형 만들기 (그리디)**

https://www.acmicpc.net/problem/1448

1448번: 삼각형 만들기

N 개의 빨대 중에 3개의 빨대를 선택해서 삼각형을 만들었을 때, 세 변의 길이의 합이 최대가 되도록.

(삼각형을 못 만들 경우 -1)

 

INPUT: 빨대 갯수, 빨대의 길이 

OUTPUT: 삼각형 세 변의 길이의 합의 최댓값. 삼각형이 성립 안 될 경우 -1 

## 백만이면 포문 한번만 돌아야 하나봄

 

https://2ssue.github.io/Algorithm/docs/baekjoon/1448.html

논리를 정리하자면, 세 변 a>b>c 를 고르면 

1. a<b+c 성립해야.

2. 큰 순으로 sort 되어 있을 때, a<b+c가 성립 안되면, 그 다음에 작은 수 a<b+c'은 당연히 삼각형도 못 만듦.

3. a<b+c가 성립되면, 가장 큰 삼각형을 구하는 것이므로 그 다음 수에 대해 고려할 필요 없음.

 

input()으로 받아오면 시간초과가 되므로, sys.stdin.readline()으로 읽어올 것

 

import sys

def solve(items):
    lines = sorted(items, reverse = True)
    ans = -1
    for i in range(len(lines)-2):
        isTrue = lines[i] < lines[i+1] + lines[i+2]
        if isTrue: 
            ans = sum(lines[i:i+3])
            break
    return ans
    
    
if __name__=='__main__':
    N = int(input())
    items = []
    for _ in range(N):
        items.append(int(sys.stdin.readline()))
    ans = solve(items)
    print(ans)