BOJ[JAVA] 1448 삼각형 만들기

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

1448번: 삼각형 만들기

 

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

public class Main {
	
	public static int [] nArr; //원본배열
	public static int [] temp; //원본배열의 복사본배열
	
	public static void main(String[] args) throws IOException {
		
		
		BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//빨대의 개수
		int n = Integer.parseInt(st.nextToken());
		
		//각 빨대의 길이
		nArr = new int[n];
		temp = new int[nArr.length];
		
		//빨대의 길이 입력받기
		for(int i=0; i<nArr.length; i++){
		
			st = new StringTokenizer(br.readLine());
			nArr[i] = Integer.parseInt(st.nextToken());
		}
		
		//병합정렬_내림차순
		mergeSort(0, nArr.length-1);
		
		
		int max = 0;
		
		for(int i=0; i<nArr.length-2; i++) {
			
			if(nArr[i] < nArr[i+1] + nArr[i+2]) {
				
				max = Math.max(max, nArr[i] + nArr[i+1] + nArr[i+2]);
				
			}
			
		}
		
		//조건으로 max==0인 이유 : 위의 if문의 조건을 만족하지못했을 때 max값 갱신이 안 되기 때문에 초기값 0을 가지고 여기로 내려온다
		//즉, 삼각형을 만들 수 없는 조건이기때문에 -1을 출력한다
		if(max==0) {
			max = -1;
		}
		
		System.out.println(max);

		 
	}
	
	//병합정렬_내림차순()
	public static void mergeSort(int start, int end) {
		
		if(start<end) {
			
			int mid = (start+end)/2; //분할할 중앙 값
			
			//구간분할
			mergeSort(start, mid); //중앙기준으로 왼쪽
			mergeSort(mid+1, end); //중앙기준으로 오른쪽
			
			int s = start; //시작지점
			int e = mid+1; //중앙기준 오른쪽 시작지점
			
			int idx = s; //증가하며 배열에 값 담기위한 변수선언
			
			while(s<=mid || e<=end) { //배열 범위 벗어나지 않도록 범위 지정 반복
				//정렬시작
				if(e>end || ( s<=mid && nArr[s]>nArr[e]) ) {
					temp[idx++] = nArr[s++];
				}else {
					temp[idx++] = nArr[e++];
				}
			}
			
			//temp에 정렬해놓은 값을 다시 원본배열에 넣기
			for(int i=start; i<=end; i++) {
				nArr[i] = temp[i];
			}
		}
	}
}