[백준] 같이 눈사람 만들래? [JAVA]

문제링크 : www.acmicpc.net/problem/20366

20366번: 같이 눈사람 만들래?

눈사람을 2개 만들기위해 눈덩이 600개 중에 서로다른 4개를 고르는 연산을 할 경우 시간초과가 난다.

 

방법은, 눈덩이 N(최대 600)개로 만들 수 있는 눈사람을 배열에 저장한다 600C2 => 600*599/2

저장할 때 어떤 눈덩이를 썼는지 같이 저장한다.(나의 경우 SnowMan 클래스의 first, second)

눈사람 크기를 기준으로 정렬한다.

 

엘자가 600C2개의 눈사람 중 만들 것을 정했을 때

안나가 크기 차이를 최소화 할 눈사람을 고를 방법은

엘자가 고른 눈사람보다 크거나 작은 눈사람 중 다른 눈덩이로 만든 최초의 눈사람을 고르는 것이다.

여기서 i~N번째까지 순차적으로 엘자가 고를 것이기 때문에 안나는 엘자보다 작은 눈사람을 탐색할 필요는 없다.

그래서 큰 눈사람 중 다른 눈덩이로 만든 최초의 눈사람을 고르기만 하면 된다.

 

 

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static int []Snow;
	public static class SnowMan{
		int height;
		int first;
		int second;
	}
	public static SnowMan []snowMan;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Snow = new int[N];
		snowMan = new SnowMan[N*(N-1)/2];
		for(int i=0;i<N;i++){
			Snow[i] = Integer.parseInt(st.nextToken());
		}
		int idx =0;
		for(int i=0;i<N-1;i++){
			for(int j=i+1;j<N;j++){
				snowMan[idx] = new SnowMan();
				snowMan[idx].first = i;
				snowMan[idx].second = j;
				snowMan[idx++].height = Snow[i]+ Snow[j];
			}
		}
		int ans = Integer.MAX_VALUE;
		Arrays.sort(snowMan,(o1,o2)->o1.height-o2.height);
		for(int i=0;i<idx-1;i++){
			for(int j=i+1;j<idx;j++){
				if(snowMan[i].first!= snowMan[j].first && snowMan[i].first != snowMan[j].second &&
						snowMan[i].second != snowMan[j].first && snowMan[i].second != snowMan[j].second){
					ans = Math.min(ans, snowMan[j].height - snowMan[i].height);
					break;
				}
			}
		}
		System.out.print(ans);
	}

}