[BOJ/PYTHON] 1448. 삼각형 만들기 (정렬)

백준 문제 링크: https://www.acmicpc.net/problem/1448

문제 요약

빨대 N개 중 3개를 선택했을 때, 세 변의 길이 합의 최댓값

핵심 아이디어

길이 합의 최대값을 구해야 하기 때문에 빨대 길이 리스트를 큰 것부터 정렬하면 된다.

삼각형은 제일 큰 변의 길이가 나머지 두 변의 길이 합보다 작을 때 성립하는데, 그 정의를 이용하면 된다.

큰 것부터 정렬된 상황이기 때문에, list[i] > list[i + 1] + list[i + 2]가 성립하면 된다.

순차 3개(a b c)가 성립 안 하면 a b d, a b e... 등의 케이스도 성립 불가해 저렇게만 보면 된다.

마지막 세 개까지 봤는데도 성립 안 하면 -1을 출력하면 된다.

풀이

# silver3-1448. 삼각형 만들기

import sys
input = sys.stdin.readline

# N개 중 3개를 선택했을 때, 세 변의 길이 합의 최댓값

n = int(put()) #빨대 갯수
length = []
for _ in range(n):
	length.append(int(input())) #빨대 길이

# 제일 긴 선분의 길이가 나머지 둘의 합보다 짧을 때 삼각형 성립
# a < b + c
# 내림차순 정렬했을 차례로 세 개가 성립하면 됨. 
# 순차 3개(a b c)가 성립 안 하면 a b d, a b e... 등의 케이스도 성립 불가
# -> 그다음 순서대로 세 개 성립하는지 검사하면 될 듯
# 실패 케이스: 마지막 세 개까지 왔는데 불가능 (-1 출력)

length.sort(reverse=True)

for i in range(n-2):
	# 성립하면 총합 출력
	if length[i] < length[i+1] + length[i+2]:
		print(length[i] + length[i+1] + length[i+2])
		break
	# 마지막까지 가도 성립 안 하면 -1 출력 
	if i == n-3:
		if length[i] >= length[i+1] + length[i+2]:
			print("-1")

실행 시간

메모리 KB, 시간 ms (python3)