[Baekjoon] 2110번 공유기 설치 (Java) 문제 풀이 [Gold 4]

문제

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

2110번: 공유기 설치

 

어떻게 풀 것인가?

처음에 감조차도 못잡았던 문제였다.

대략 1시간정도의 고민 끝에 다른 분의 풀이를 참고했다.

아마 이번 포스팅은 풀이보다는 회고 느낌으로 작성을 해야할 것 같다.

 

이 문제는 "이분탐색"을 물어보는 문제였다.

 

그렇다면 이러한 이분탐색을 어디에 활용할 수 있었을까?

'최소 거리에 대해 설치 가능한 공유기'가 문제에서 주어지는 '설치 해야 할 공유기의 개수(M)'와 같은 거리 중 최대로 가질 수 있는 '최소 거리'를 이분탐색을 통해서 찾는 것이다. 즉, 거리를 탐색 범위로 잡고 이분탐색을 하면서, 해당 거리에 대해 설치 가능한 공유기의 개수에 따라 탐색하는 거리의 범위를 좁혀나가야 했다.

 

이러한 부분이 생각보다 까다롭다고 생각했다.

그리고 반대로 이분탐색에 대해서 잘 알고 있다면 쉽게 접근이 가능한 문제였다.

 

풀면서 놓쳤던점

문제의 유형을 파악하지 못함.

 

이 문제를 통해 얻어갈 것

이분탐색

 

내 코드 

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

class Main {

    public static int[] house;

    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 M = Integer.parseInt(st.nextToken());

        house = new int[N];

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

        Arrays.sort(house);


        int lo = 1;
        int hi = house[N - 1] - house[0] + 1;

        while (lo < hi) {

            int mid = (hi + lo) / 2;
            if (canInstall(mid) < M) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        System.out.println(lo - 1);
    }

    public static int canInstall(int distance) {

        int count = 1;
        int lastLocate = house[0];

        for (int i = 1; i < house.length; i++) {
            int locate = house[i];

            if (locate - lastLocate >= distance) {
                count++;
                lastLocate = locate;
            }
        }
        return count;

    }
}

 

참고

https://st-lab.tistory.com/277

[백준] 2110번 : 공유기 설치 - JAVA [자바]