★ [백준][Java] 2110번 공유기 설치 (이진탐색) #2

#2

처음 시작할 때 공유기 1개 박고 시작(count = 1로 시작)

다음 공유기 좌표인 nextCoord 변수를 활용하여

문제에서 익힌대로 해결함

 

 

 

솔직히 좀 어려웠다..

 

문제 이해가 안됐음 이진탐색이라는 태그를 알고 풀어도 안풀림

결국 이진탐색에서 기준으로 잡을 값을 무엇으로 놓느냐인데

문제에서 요구하는 집과 집 사이의 최대값이 대체 어떻게 설정해야 하는지..

다른 풀이를 보고 나서 이해함

 

아예 풀이 시작부터 그 집과 집 사이의 거리값을 지정해놓고

현재 지점(공유기를 설치한 집 중에서 가장 좌표값이 낮은 부분)에서 그 거리값을 더한 부분

Line:34 nextModem이라는 변수값인데 이것이 의미하는 바는

현재 지점에서 그 거리값에서 멀어진 좌표라는 의미인데 반드시 이 좌표에 집이 있을 필요는 절대 없음

그 좌표를 기준으로 더 멀어져도 거리값을 만족하는 것임

그니까 .. 그 거리값이라는 것이..

공유기를 설치한 집과 또 다음 공유기를 설치한 집의 최소 거리라는 것임 그 이상이 되도 조건을 만족하는 것임

하지만 또 다음 조건인 count(공유기를 주어진 마지막 집까지 갔는데도 전부 설치를 했느냐 안했느냐)가 있고

또 count를 만족하더라도 계속 그 조건을 만족하는 거리값의 이상적인 값(문제에서 요구하는 최대값..)을

UpperBound로 찾아주는거임

 

요약

1. 거리값은 이진탐색의 고정된 mid값이고 집의 좌표배열(sorted된)을 찾아가면서 

   공유기를 설치할 수 있는(거리값 이상으로 떨어진) 집을 발견했을 때 count++과 함께

   다음 공유기 이상 좌표를 새로 갱신해줘야함

2. count값의 초기값은 1임 (맨처음 house[0]은 공유기를 설치하고 시작해야함)

 

 

 

근데 보고도 실수를 또함

Line:35에 cnt를 1로 시작해야하는데 그 이유는

가장 첫 시작점인 집(좌표값이 가장 낮은)은 무조건 공유기를 깔고 들어가기 때문이다

 

 

참고 : https://dundung.tistory.com/54

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        int C = stoi(str[1]);
        
        int[] house = new int[N];
        for(int i=0; i<N; i++)
            house[i] = stoi(br.readLine());
        
        Arrays.sort(house);
        
        int left = 1;
        int right = house[house.length-1] - house[0];
        
        int res = 0;
        while(left<=right) {
            int mid = (left+right)/2;
            
            int nextModem = house[0] + mid;
            int cnt = 1;
            for (int i : house) {
                if(i>=nextModem) {
                    cnt++;
                    nextModem = i+mid;
                }
            }
            
            if(cnt<C)
                right = mid-1;
            else {
                left = mid+1;
                res = mid;
            }
        }
        
        System.out.println(res);
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}