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

날짜	분류	번호	알고리즘 분류	링크
21-01-19	BOJ	20366	이분탐색	www.acmicpc.net/problem/20366

 

 

 

문제 요약

1. N개의 눈덩이 중 4개를 골라 눈두덩이 2개로 만들어진 눈사람 2쌍을 만든다. 이중 두 눈사람의 키 차이가 최소가 되는 값 구하기
2. 눈덩이의 키 = 지름

 

풀이

1. 눈덩이의 키 순서로 정렬
2. 정렬된 상태에서 a, b, c, d 순차적으로 골랐다고 가정했을 때 a+d와 b+c의 차이가 abcd로 만들수 있는 눈사람의 키 차이임
3. a, b, d를 3중 for문으로 돌리고(ㅌㅋㅋㅋ ㅠㅠ ) 나머지 c를 b+1과 d-1 사이에서 c의 값 찾기...
   • lower bound로 c의 값 구함
   • c-1의 값도 고려함 (c-1와 a, b, d가 다를 경우에만)

 

비고

• N이 600인데 시간 제한이 2초라 3중 for문이 가능했던 것 같다... ^^

 

 

package b20.BOJ_20366_같이눈사람만들래;

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		int[] ball = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			ball[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(ball);

		int answer = Integer.MAX_VALUE;
		for (int a = 0; a < N - 3; a++) {
			for (int b = a + 1; b < N - 2; b++) {
				for (int d = N - 1; d > b + 1; d--) {
					int c = search(ball, b + 1, d - 1, ball[a] + ball[d] - ball[b]);
					answer = Math.min(answer, Math.abs((ball[a] + ball[d]) - (ball[b] + ball[c])));
					if (c - 1 != a && c - 1 != b && c - 1 != d)
						answer = Math.min(answer, Math.abs((ball[a] + ball[d]) - (ball[b] + ball[c - 1])));
				}
			}
		}
		System.out.println(answer);
	}

	private static int search(int[] ball, int l, int r, int target) {
		while (l < r) {
			int mid = (l + r) / 2;
			if (ball[mid] < target)
				l = mid + 1;
			else
				r = mid;
		}
		return l;
	}

}