[BOJ] 2110 - 공유기 설치 JAVA

www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3

1

2

8

4

9

예제 출력 1

3

 

 

 

 

 

 

풀이 .

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

public class Main {
    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());
        int c = Integer.parseInt(st.nextToken());
        int[] houses = new int[n];
        for(int i = 0; i < n; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(houses);
        long min = 1;
        long max = houses[n-1] - houses[0];
        long mid = (min + max) / 2;

        long ans = 1;
        while(min <= max) {
            long cnt = 1;  // 맨 처음 집은 처음부터 포함
            int previous = houses[0];  // 최근에 공유기를 놓은 집
            for(int i = 1; i < n; i++) {
                int dist = houses[i] - previous;  // 최근에 공유기 놓은 집부터 다음 타겟 집까지의 거리
                if(dist >= mid) {  // 무작정 mid 간격으로 놓는 것이 아니다
                    previous = houses[i];
                    cnt += 1;
                }
            }

            if(cnt >= c) {
                ans = Math.max(ans, mid);
                min = mid + 1;
            }else {
                max = mid - 1;
            }
            mid = (min + max) / 2;
        }
        System.out.println(ans);
    }
}

 

다른 이분탐색 문제보다 더 어려웠다.

 

공유기를 두는 최소간격의 최대를 구해야 한다. (공유기 사이의 간격은 적어도 K만큼 떨어져있어야 한다. 이때 K의 최대)

처음에는.. 무작정 mid 간격마다 공유기를 놓아서 구간 안에 들어가는 공유기의 개수만 C에 맞춰주면 된다고 생각했다.

 

그런데 이런 방식으로 짜면.. 들어가는 공유기의 개수 자체는 맞출 수 있지만 공유기 사이의 최소간격의 최대를 구할 수는 없다.

왜냐하면 집이 없는 좌표에는 공유기를 놓지 않기 때문이다.

 

공유기는 반드시 집이 있는 좌표에만 들어갈 수밖에 없다.

 

가장 최근에 공유기를 놓은 좌표를 저장하고 다음 집까지의 거리를 구했다. 그 거리가 mid를 넘어가지 못한다면 공유기를 놓지 않고 그 다음 집을 타겟으로 삼았다.

 

최근에 공유기를 놓은 집과 타겟으로 삼은 집 사이의 거리가 mid 이상일 때만 타겟지점에 공유기를 놓을 수 있다.

(처음에 짠 코드는 그냥 무작정 mid 칸 이후에 공유기를 놓아서 집이 아닌 곳에도 공유기를 놓았다.)