[Baekjoon] 1448번 : 삼각형 만들기

1. 문제

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

• 그리디 문제

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

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

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

// 예제 입력 1 
3
1
2
3

// 예제 출력 1 
-1

// 예제 입력 2 
3
1
2
2

// 예제 출력 2 
5

// 예제 입력 3 
6
2
3
2
3
2
4

// 예제 출력 3 
10

// 예제 입력 4 
5
4
5
6
7
20

// 예제 출력 4 
18

2. 핵심 아이디어

• 삼각형의 세 변 중 가장 긴 변의 길이는 나머지 두 변의 길이의 합보다 작다.

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = []

for i in range(n) :
  arr.append(int(input()))
  
arr.sort(reverse=True)
ck = False

for i in range(len(arr)-2) :
  if arr[i] < arr[i+1] + arr[i+2] :
    print(arr[i] + arr[i+1] + arr[i+2])
    ck = True
    break
    
if ck == False :
  print(-1)

4. Java 문제풀이