[python] 백준 1448. 삼각형 만들기

문제

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

세준이는 N개의 빨대를 가지고 있다. N개의 빨대 중에 3개의 빨대를 선택했을 때, 이 빨대로 삼각형을 만들 수 있다면, 세 변의 길이의 합의 최댓값을 구하고 싶다.

입력

첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 삼각형 세 변의 길이의 합의 최댓값을 출력한다. 만약 삼각형을 만들 수 없으면 -1을 출력한다.

---

풀이

스흡... 코드 정리에 앞서 조금... 효율적인 코드였는지는 모르겠다~ 정도로 밑밥을 깔고 이야기를 해보겠다. 일단 이 문제는 삼각형이 될 수 있는 공식만 알고 있다면 쉽게 풀 수 있는 문제였다.

 

가장 긴 변의 길이가 나머지 변의 길이의 합보다 작으면 삼각형이 될 수 있다!

결국에는 입력받은 길이들을 오름차순으로 정렬한 다음, 맨 뒤부터 pop을 하면서 삼각형이 되는 값을 찾자마자 break을 해 while문을 빠져나오면 되겠다!

같은 아이디어로 코드를 짜서...

import sys

n = int(sys.stdin.readline().strip())
num = []
sum = []

for i in range(n):
    num.append(int(sys.stdin.readline().strip()))

num.sort()

while True:
    if len(num) <= 2:
        sum.append(-1)
        break
    else:
        a = num.pop()
        b = num.pop()
        c = num.pop()
        if a < b + c:
            sum.append(a+b+c)
            break
        elif len(num) == 0:
            sum.append(-1)
            break
        else:
            num.append(c)
            num.append(b)
            continue

sys.stdout.write(str(max(sum)))

 

요런 답이 나왔다.

 

1. 삼각형이 될 수 없는, 즉 세 변의 길이가 배열에 남아있지 않았을때 -1을 출력할 수 있도록 만들었다.

2. 또, 비교를 위해 내보냈던 a,b,c중 a제외 나머지는 가장 긴 변이 될 수 있으므로 c -> b 순으로 append해주고

3. 삼각형 조건에 해당하는 값이 나오면 break로 빠져나오게 했다.

 

처음 나온 값이 최대값이 될 수 있는 이유는, 이 모든 걸 하기 전에 정렬로 오름차순을 해놨고... 1번째로 찾아지는 값이 결론 적으로는 가장 긴 변들을 포함하고 있는 거기 때문이다.

 

시간 복잡도

이번 문제의 시간 복잡도는 O(n log n)이다. 사실 while문이 가장 오래 걸리는 시간 복잡도이지 않을까... 같은 생각을 했는데...생각을 다시 해보니 결국 도는 건... 리스트 한 번이다. O(n) 이라는 뜻.

 

그렇다면 O(n log n)은 어디서 왔냐... 바로 오름차순으로 정렬해준 과정에서 걸리는 시간 복잡도다.

 

---

풀어야 할 문제가 산더미~ 얼른 하러 가자~!