백준 [자바 java] 공유기 설치

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

2110번: 공유기 설치

오랜만에 백준이다! 코드트리를 통해서 개념을 어느정도 익혔으니 실전에 적용해보는 연습을 슬슬 해보려고 한다.

 

이 문제는 내가 5개월 전에 시도했다가 못풀었던 문제이다.

집의 위치와 공유기의 수가 주어지고, 이를 적절하게 배치해서 공유기가 설치된 집 사이의 가장 가까운 거리가 최대가 되도록 해야한다.

 

 이 문제는 이진탐색으로 풀었고, lowerBound 개념이 들어간다. 이진 탐색을 통해서 가장 가까운 거리의 최댓값을 탐색했다. mid값이 가장 가까운 거리의 최대라고 했을 때 공유기를 배치해보고 공유기의 수가 주어진 c보다 크거나 같다면 유효한 값이라는 의미이므로, ans값을 갱신한다. 

 

공유기를 배치할 때에는 무조건 첫번째 집에는 설치된다고 가정하였다. 만약 첫번째 집에 설치하지 않는다면 전체 거리가 두번째 집 ~ 마지막집이 되므로 비효율적이기 때문이다.

 

내가 이 문제를 풀면서 두 가지 실수를 했다.

1. 이진탐색을 할 때 while값에 (left < right)를 하는 바람에 left == right인 경우가 고려되지 않았다. 나는 left와 right모두 mid + 1, mid-1을 하기 때문에 꼭 < 대신 <= 를 사용해야 한다.
2. right의 값을 n으로 지정했었다. mid는 공유기가 설치된 집 사이를 의미하므로 고려해봐야할 거리의 최댓값인 arr[n-1]을 넣었어야 했다.

import java.awt.*;
import java.io.*;
import java.util.*;
import java.math.*;

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[] arr = new int[n];

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int left = 0;
        int right = arr[n-1];
        int mid = 0;

        int ans = 0;

        while(right >= left){
            mid = (left + right)/2;

            int now = 0;
            int cnt = 1;

            for(int i = 1;i<n;i++){
                if(arr[i] - arr[now] >= mid){
                    now = i;
                    cnt++;
                }
            }

            if(cnt < c) right = mid -1;
            else{
                left = mid +1;
                ans = Math.max(mid, ans);
            }
            //System.out.printf("%d %d\n",left,right);
        }

        System.out.println(ans);

    }
}