https://www.acmicpc.net/problem/1448
1448번: 삼각형 만들기
첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다
www.acmicpc.net
삼각형의 세 변의 길이를 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)
'알고리즘💻 > 이분탐색&정렬&분할정복' 카테고리의 다른 글
BOJ 1377번: 버블 소트 (0) | 2021.07.19 |
---|---|
BOJ 11582번: 치킨 TOP N (0) | 2021.07.19 |
BOJ 10825번: 국영수 (0) | 2021.07.18 |
BOJ 18870번: 좌표 압축 (0) | 2021.05.05 |
BOJ 2805번: 나무 자르기 (0) | 2021.01.29 |