BAEKJOON #1448) 삼각형 만들기 (python)

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

1448번: 삼각형 만들기

알고리즘 분류: 그리디

 

💡 풀이

import sys
n = int(input())
list = []
answer = -1

for _ in range(n):
    list.append(int(sys.stdin.readline()))
    
list.sort(reverse=True)

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

• 삼각형을 만들 때, 삼각형의 길이의 합의 최대값을 요구하므로, 받은 빨대의 길이를 내림차순으로 정렬한다.
• 정럴 후 차례대로 돌면서 삼각형이 만들어질 수 있는지 확인한다.
  → 삼각형은 한 변의 길이가 다른 두 변의 길이의 합보다 크거나 같으면 삼각형이 성립할 수 없다는 결정조건을 가진다.
• 만들어지는 삼각형을 찾으면 answer에 세 변의 길이의 합을 할당하고 break한다.

 

이 문제는 삼각형의 결정조건만 파악하고 어렵지않게 풀 수 있었다.

처음에는 input()으로 입력받았더니 시간초과가 떴서 당황했지만 다시 sys를 import해서 입력받아주니 잘 돌아갔다.

앞으로는 여러 개의 수를 입력받을 때에는 sys.stdin.readline() 사용!!