공유기 설치 ( 백준 2110 )

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

 

* 문제가 이해 안가서 GPT 코드를 보고 이해한 문제

* 문제를 요약하자면 1부터N까지의 좌표가 존재

* 집의 갯수 N과 설치해야 할 공유기 K가 첫줄에 주어진다

* 둘쨋줄 부터 집의 좌표가 순서대로 주어진다

* 출력 조건이 문제에서 나와있기로는 '첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.' 되어있는데.

* 코드를 보고 해석해본 바로는 다음과 같다.

 

* 각 공유기 마다 최대 거리를 계산하고, 그 중에서 공유기 끼리 가장 인접한 거리를 반환하는 것이다.

* 따라서 Parametric Search 를 이용해서 공유기 갯수를 비교한다음 범위를 좁혀나가면 되는것이다.

 

* decision() 함수는 늘 그랫듯이 시작과 끝지점을 더해서 반으로 나누면 된다.

* 아래는 decions() 함수의 설명이다.

 

 

 

 

* 첫 집과 마지막집을 left, right로 설정하고 반으로 나누면 mid값이 할당된다.

* 다음에 2중 for 루프로 반복하면서 집 2개의 차이가 mid 값보다 큰 경우를 생각해야한다.

* 큰 경우가 공유기를 설치 가능한 조건이라서 설치 좌표를 갱신하고 횟수를 1 증가시킨다.

 

완성 코드는 참조하기 바란다.

import java.io.*;
import java.util.*;

public class BOJ2110 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int house = Integer.parseInt(st.nextToken());
        int install = Integer.parseInt(st.nextToken());
        int[] houses = new int[house];
        for(int i = 0; i < house; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(houses);
        parametric(houses, install);
    }
    private static void parametric(int[] houses, int install) {
        int left = 1, right = houses[houses.length-1] - houses[0], result = 0;
        while(left <= right) {
            int mid = (left + right)/2;
            if(canInstall(houses, mid, install)) {
                result = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
    private static boolean canInstall(int[] houses, int mid, int install) {
        int lastInstall = houses[0], cnt = 1;
        for(int i = 1; i < houses.length; i++) {
            if(houses[i] - lastInstall >= mid) {
                lastInstall = houses[i];
                cnt++;
            }
        }
        return cnt >= install;
    }
}

 

* return 조건도 현재 설치한 공유기 수가 같거나 많을때를 반환한다.

* 전에 나무 자르기에서도 이야기 했듯이 최대한 많은 길이를 할당해야하기 때문에 공유기가 많을때 참을 반환한다.

끝