백준 1448

• 실버 3단계 문제

풀이)

삼각형 변의 길이 합 최대를 구하면 되기 때문에, 입력받은 변수 중 가장 길이가 큰 것들부터 골라 계산하면 된다.

삼각형이 될 수 없는 조건은 '가장 긴 변의 길이 >= 나머지 두 변의 길이 합' 이다.

주의할 점)

너무 쉬워서 왜 실버 3단계일까 생각해봤는데, 해당 문제는 그리디 알고리즘을 활용했기 때문인듯 하다.
원시적으로 최소의 선택으로 최대의 값을 찾기 위한 문제는 그리디 알고리즘으로 접근하자는 생각을 갖자.

내 코드)

import java.io.*;
import java.util.*;

public class Backjoon1448 {
	public static void main(String[] args) throws IOException {
		
		//입력 받기.
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
	
		ArrayList<Integer> arr = new ArrayList<>();
		for(int i=0;i<N;i++) {
			arr.add(Integer.parseInt(bf.readLine()));
		}
		arr.sort(Comparator.reverseOrder());
		
	    int result = -1;
		for(int i=0;i<N-2;i++) {
			if(arr.get(i) >= (arr.get(i+1) + arr.get(i+2))) {
				continue;
			}
			else {
				result = arr.get(i+1) + arr.get(i+2) + arr.get(i);
				System.out.println(result);
				return;
			}
		}
		System.out.println(result);
	}
}