[BOJ-20366] 같이 눈사람 만들래?(Java)

백준 20366 같이 눈사람 만들래?

 

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

 

문제 설명

 

 - 엘자와 안나는 N개의 눈더이가 있다.

 

 - 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이 보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만든다.

 

 - 눈덩이의 키는 두 눈덩이 지름의 합과 같다.

 

 - 엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 1개씩, 총 2개를 만들려고 한다.

 

 - 두 자매는 두 눈사람의 키의 차이가 작을 수록 두 눈사람의 사이가 좋을 것이라고 믿는다.

 

 - 엘자와 안나가 가장 사이 좋은 눈사람을 만들 수 있게 도와주려한다.

 

 - 주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하라.

---

 

입력 값

 

 - 첫째 줄에 N(4<=N<=600)이 주어진다.

 

 - 둘째 줄에는 각 눈덩이 i(1<=i<=N)의 지름을 의미하는 정수 Hi(1<=Hi<=$10^9$)가 공백으로 구분되어 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제에서 주요한 점은 두 눈사람의 차이를 최소로 만들어야 한다는 것이다.

 

 - 즉, 모든 경우를 탐색하여 눈사람의 차이를 최소로 만들면 된다.

 

 - 먼저 엘자가 만들 수 있는 모든 눈사람을 구한다.

 

 - 이때 시간 복잡도는 O($N^2)이다. 즉, 600x600 = 360,000이 된다.

 

 - 그리고 안나가 만들 수 있는 눈사람을 구하면 된다.

 

 - 이때 안나가 선택할 위 눈덩이를 선택하는 경우의 수는 O(N)이 된다.

 

 - 그리고 안나가 선택할 아래 눈덩이는 눈사람의 차이가 최소가 되는 값을 선택하면 된다.

 

 - 이 눈덩이는 위 눈덩이 보다 커야 하고, 최소 값이 되는 것을 찾아야 한다.

 

 - 모든 눈덩이를 살펴보게 되면 O(N)의 시간 복잡도가 들지만, 정렬이 되어 있다면 O(logN)의 시간복잡도가 들게 된다.

 

 - 즉, 최종적으로 시간복잡도는 O($N^3$logN)이 된다.

 

 - 여기서 엘자가 선택할 위 눈덩이를 인덱스를 i, 아래 눈덩이 인덱스를 j 라고 하고

  안나가 선택할 위 눈덩이 인덱스를 k, 아래 눈덩이 인덱스를 p라고 하자.

   그러면 k < i < j < p 이거나 i < k < p < j, i < k < j < p 중 하나이기 때문에 범위를 제한할 수 있다.

 

---

 

 

소스 코드

 

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

public class Main {
	public static int heights[] = new int[601];
	public static int N ;

	public static void main(String[] args) throws IOException{

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(bf.readLine());

		int result = Integer.MAX_VALUE;

		Arrays.fill(heights, Integer.MAX_VALUE);

		StringTokenizer st = new StringTokenizer(bf.readLine());

		for(int i=0;i<N;i++){
			heights[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(heights);

		for(int i=0; i<N; i++){
			for(int j=i+1;j<N;j++){
				for(int k=0;k<j;k++){
					if(i==k){
						continue;
					}
					int num = heights[i]+heights[j]-heights[k];
					// k i j
					if(k < i) {
						result = Integer.min(result, binary(i+1, j-1, num));
					}
					// i k j
					else{
						result = Integer.min(result, binary(k+1, j-1, num));
					}
					result = Integer.min(result, binary(j+1, N-1, num));
				}
			}
		}

		System.out.println(result);

	}

	public static int binary(int start,int last, int num) {
		int result = Integer.MAX_VALUE;
		while(start <= last){
			int mid = (start + last)/2;
			result = Integer.min(result, Math.abs(heights[mid] - num));
			if(num == heights[mid]){
				return 0;
			}
			if(num < heights[mid]){
				last = mid-1;
			}
			else{
				start = mid+1;
			}

		}
		return result;
	}

}