[자바] 백준 1448 - 삼각형 만들기 (java)

 문제 : boj1448

---

 

필요 알고리즘 개념

• 그리디, 정렬
  
  • 그리디로 접근해서 풀 수 있다.
• 수학
  • 삼각형의 세 변을 이루는 규칙을 알아야 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  삼각형의 세 변을 이루는 규칙만 알면 풀 수 있다. 간단한데, 가장 긴 변이 있을 때 나머지 두 변의 합이 가장 긴 변의 길이보다 커야 한다. 아래 이미지를 보면 이해 가능할 것 같다.

 

  그리고 이 문제에서 원하는건 '삼각형을 만들 수 있는 세 변 중, 길이의 합의 최대치' 이다. 결국 만들 수 있는 삼각형 중 긴 변이 클수록 당연히 좋고, 나머지 두 변도 클수록 좋다.

 

  그러므로 우선 내림차순으로 정렬한 후, 큰 순서대로 3개씩 보면서 확인하면 된다. 예제 입력 4를 보자.

5
4
5
6
7
20

 

  내림차순으로 정렬하면 아래와 같다.

 

  가장 세 변의 길이가 큰 경우는 가장 큰 3개의 수를 고르는 경우이다. 하지만 이 경우 가장 긴 변이 나머지 두 변의 합보다 크기때문에 삼각형이 불가능하다.

 

  따라서 다음으로 크게 만들 수 있는 세 변은 아래와 같다. 이 경우는 삼각형이 가능하므로 합인 18을 출력해주면 된다.

 

  이런식으로 3개씩 끝까지 보는 동안 가장 긴 변보다 나머지 두 변의 합이 큰 경우를 못찾았다면 -1을 출력해주면 된다.

 

---

 

코드 : github

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        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);
    }
}