BOJ 1448 - 삼각형 만들기

문제

N개의 빨대 중 3개를 골라 삼각형을 만들 수 있을 때, 둘레의 최댓값을 구하라.

입력

첫째 줄에 N, 이후 N줄에 빨대 길이가 주어진다.

출력

삼각형 둘레의 최댓값을 출력한다. 만들 수 없으면 -1을 출력한다.

예제

입력	출력
`3` `1` `2` `3`	`-1`

풀이

정렬 후 큰 쪽부터 연속 3개를 확인하여 삼각형 조건을 만족하는 첫 번째 조합을 찾는다.

빨대 길이를 오름차순 정렬한다
가장 큰 쪽부터 연속 3개를 검사한다 (arr[i] + arr[i+1] > arr[i+2])
조건을 만족하면 세 변의 합이 최대 둘레이다

핵심 아이디어: 정렬 후 연속 3개가 삼각형 조건을 만족하면 그것이 최대 둘레이다. 연속하지 않은 조합은 반드시 둘레가 더 작다.

코드

package day549;
 
import java.io.*;
import java.util.*;
 
public class Day523BOJ1448삼각형만들기 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    while (n-- > 0)
      arr[n] = Integer.parseInt(br.readLine());
    Arrays.sort(arr);
    for (int i = arr.length - 3; i >= 0; i--) {
      if (arr[i] + arr[i + 1] > arr[i + 2]) {
        System.out.println(arr[i] + arr[i + 1] + arr[i + 2]);
        return;
      }
    }
    System.out.println(-1);
  }
}

복잡도

시간: O(N log N)
공간: O(N)

문제