[백준][BOJ 1448] - 삼각형 만들기

문제

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

1448번: 삼각형 만들기

 

 

문제 접근

• 삼각형 세 변의 길이의 합의 최댓값을 구해야 한다. 이때 삼각형의 조건을 만족할 수 있어야 한다.
  • 즉 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작아야 한다는 조건을 만족해야 한다.
• 가장 나이브한 풀이는 완전 탐색을 사용하여 N개 빨대 중 3개를 선택하여 삼각형의 조건에 부합하는지를 검사하고, 통과한다면 그 합을 구해 최대 값을 갱신하는 방식이다. 하지만 여기서는 $3 \leq N \leq 1,000,000$ 이라는 조건 때문에 시간복잡도가 매우 커져 시간 초과가 나는 방식이다.
• 다른 방식은 세 변의 길이 합의 최대값을 구한다는 것에 주목해, 각 빨대의 길이를 정렬하는 것이다. 그 이후에는 3개씩 슬라이딩 윈도우 방식을 사용해 삼각형의 조건에 맞는지를 검사하는 것이다. 다음의 예제를 보자.

5
4
5
6
7
20

• 해당 데이터들을 정렬하면 4 5 6 7 20 이 된다. 이제 여기서 변의 합의 최대값을 구해야 하므로 가장 큰 수들부터 확인한다. 정렬되어있기 때문에 여기서는 20 7 6 이 선택될 수 있다.
  • 이때 $20 \geq 7 + 6$ 이기 때문에 삼각형의 조건을 만족시킬 수 없다.
• 그 다음으로는 7 6 5가 될 수 있다. 이 수들은 삼각형의 조건을 만족하기 때문에 3개의 합인 18을 얻을 수 있다. 이때 우리는 이미 정렬을 수행했기 때문에 갈수록 수가 작아진다는 것을 알 수 있다. 따라서 지금 구한 이 18이 최대 합이란 것을 확인할 수 있다. 따라서 정답은 18이 된다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int[] data = new int[N];

    for (int i = 0; i < N; i++){
      data[i] = Integer.parseInt(br.readLine());
    }

    Arrays.sort(data);

    for (int i = data.length - 1; i >= 2; i--){
      int line1 = data[i];
      int line2 = data[i - 1];
      int line3 = data[i - 2];

      if (line1 >= line2 + line3){
        continue;
      }

      System.out.println(line1 + line2 + line3);
      return;
    }

    System.out.println(-1);
  }
}