[Python] 1448번 삼각형 만들기

✏️ 문제

 

문제 파악

중요한 삼각형의 조건은 다음과 같다.

" 가장 긴 변은 다른 두 변의 합보다 작다. "

이 조건을 만족하게 코드를 짜면 쉽게 해결할 수 있는데 삼각형 세 변의 길이의 합이 최대로 되려면 3연속인 값을 써야한다는 생각을 못하고 3중 for반복문을 썼더니 시간초과가 계속 떴었다 ㅠㅠ..

근데 3연속인 값을 안썼을 때 합이 최대가 되는 세 변의 길이는 진짜 없을까...?

 

알고리즘

• 그리디 알고리즘
• 정렬
• 수학

 

코드

import sys
input = sys.stdin.readline

n = int(input())
length = sorted([int(input()) for _ in range(n)], reverse=True)
result = -1

for i in range(n-2):
  if length[i] < length[i+1] + length[i+2]:
    result = length[i] + length[i+1] + length[i+2]
    break
 
print(result)