[Java] 백준 1448 번 (삼각형 만들기)

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

1448번: 삼각형 만들기

알고리즘 분류

• 수학
• 그리디
• 정렬

 

풀이

그리디 알고리즘과 정렬을 이용해 문제를 풀었다.

먼저 삼각형의 성립 조건을 알아야 한다.

삼각형의 성립 조건: a, b, c(가장 긴 변)이 있을 때 a + b > c 이어야 삼각형이 성립이 된다.

 

그래서 입력받은 배열을 정렬 후

뒤에서부터 차례로 삼각형이 성립이 되는지 if 조건문을 사용해 구했다.

Arrays.sort(arr);
 
for (int i = arr.length -1 ; i >=2 ; i--) {
      int c = arr[i];
      int b = arr[i-1];
      int a = arr[i-2];
 
      if (a+b > c){
         System.out.println(a+b+c);
         return;
      }
 
} // for

 

 

아래는 전체 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
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 [] arr = new int [n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        Arrays.sort(arr);
 
        for (int i = arr.length -1 ; i >=2 ; i--) {
           int c = arr[i];
           int b = arr[i-1];
           int a = arr[i-2];
 
            if (a+b > c){
                System.out.println(a+b+c);
                return;
            }
 
        } // for
        System.out.println("-1");
    } // main
}