BOJ 1448: 삼각형 만들기

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

1448번: 삼각형 만들기

삼각형의 세 변의 길이를 a, b, c라고 하고 그 중에 제일 긴 변의 길이가 c 라고 할 때 a+b > c 라는 조건을 만족해야 삼각형이 성립할 수 있다.

 

입력받은 빨대의 길이를 오름차순으로 정렬하고 제일 긴 빨대(arr[-1])부터 c라고 했을 때 가능한 모든 경우를 탐색해봤는데.. 당연히 시간초과가 났다. 중간에 break문을 넣어도 시간초과가 났다.

 

다시 한 번 생각해보니.. 삼중 for문을 이용하는 게 바보같은 짓이었다..😭

빨대의 길이를 오름차순 정렬 해놓았으니까 제일 긴 변의 길이를 c라고 하고 그 다음으로 긴 변의 길이를 b, 그 다음을 a라고 하면 a+b < c 인경우에는 그 뒤의 것들을 탐색해볼 필요가 없이 그 c를 이용해서는 삼각형이 만들어지지 않는 것이다...

 

이렇게 간단한 문제를 삽질하다니.. 생각하자 생각!!!

import sys

N = int(sys.stdin.readline())
arr = []
for _ in range(N):
    arr.append(int(sys.stdin.readline()))

arr.sort()
ans = 0

for i in range(N-1,1,-1):
    c = arr[i]
    b = arr[i-1]
    a = arr[i-2]
    if (a+b>c):
        ans = a+b+c
        break
if (ans==0): print(-1)
else: print(ans)