백준_1448 삼각형 만들기(자바) / 그리디

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class Back_1448 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		Integer arr[] = new Integer[N];
		
		for (int i = 0; i < N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		int max = 0;
		Arrays.sort(arr,Collections.reverseOrder());
		
		for (int i = 0; i < N-2; i++) {
			if(arr[i]<arr[i+1]+arr[i+2]) {
				max = Math.max(max, arr[i]+arr[i+1]+arr[i+2]);
			}
		}
		if(max==0) {
			max=-1;
		}
		System.out.println(max);
	}
}

 

※ 내 생각

이 문제는 그리디 알고리즘을 활용하는 문제입니다.

삼각형의 조건은 가장 큰 길이의 변 < 나머지 두개의 변의 합
이 조건이 성립해야 합니다.

그리디 알고리즘으로 정렬을 진행한 후에
가장 큰 값부터 순서대로 3개의 값만 비교하면서 for문을 돌려주면 됩니다.