[JAVA][백준 2110] 공유기 설치

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

---

저번에 풀었던 문제인 나무 자르기와 비슷한 문제이다.

사실 공유기 설치는 이전에 한번 시도했었는데 실패하고 나무자르기라는 문제가 더 쉽다고 해서 나무자르기로 연습한번 하고 다시 풀어 볼려고 한다.

↓ 나무 자르기 포스팅

https://bitj-bitbox.tistory.com/18

[JAVA][백준 2805] 나무 자르기

---

풀이 과정

이게 신기한게 그냥 이 문제만 봤을땐 문제를 어떻게 풀어야할지 감이 하나도 안왔었는데
나무 자르기를 풀어보고 오니 방법이 보인다.

 

공유기를 설치하는 간격(mid)을 이분탐색으로 구하고,

공유기를 C개를 설치했을 경우, 가장 인접한 두 공유기 사이의 거리(가장 가까이 있는 공유기 설치 간격)가 최대가 되는 mid를 찾는 코드를 짜면 된다.

 

또한, 공유기를 최대한 많이 설치하려고 하기때문에 mid간격으로 설치했을때 C개 이상의 공유기를 설치할 수 있어야한다.

 

 

일단 집의 좌표가 오름차순으로 주어지는 것이 아니기때문에 정렬을 해주고 시작.

왜냐하면 이분 탐색 자체가 정렬되어있는 값에서 탐색할때 사용하는 알고리즘이기 때문

 

이 문제의 핵심은 모든 공유기 사이의 간격이 적어도 mid 이상인지 확인하는 것이다. 

 

1. 최소로 설정할 간격을 정하고(mid) 해당 간격보다 더 멀리 있는 집에만 공유기 설치

-> mid가 의미하는 것이 우리가 이 mid값보다 가까이에는 공유기를 설치하지 않을거다!! 라고 설정한 것

2. 설치할 수 있는 모든 집에 설치 한 후,

설치한 공유기 개수가 설치하려는 공유기의 개수(C)보다 많으면

너무 많이 설치할 수 있다는 뜻.

즉, 간격을 너무 좁게 설정했다는 뜻이므로

mid값을 늘려줄 수 있도록 left를 mid + 1로 두고 다시 이분탐색

다음 반복을 하기 전에 어쨌든 설치할 수 있다는 뜻이므로 result에 해당 값(mid)를 기록해둔다.

(이렇게 하면 결국 최적의 순간에 최적의 값을 결과로 저장한다.)

설치한 공유기의 개수가 설치하려는 공유기의 개수보다 적으면

간격이 너무 넓어서 공유기를 덜 설치했다는 뜻이므로 간격을 좁혀준다.

 

 

예시1번을 보면

정렬후 1, 2, 4, 8, 9 이렇게 배열에 정렬되어 있을 것이다.

1. 첫 번째 반복

left = 0, right = 9 로 시작을 할텐데

(풀이를 쓰다가 생각이 난게 최소간격은 어쨌든 1일 것이고 최대 간격은 arr[N-1] - arr[0]이겠네..

저렇게 해도 어쨌든 최적의 mid값을 찾기 때문에 문제는 없겠지만 효율성에서 문제가 있을 수도 있을 것 같다)

left = 1, right = 9 - 1 로 시작!

첫 번째 반복에서 mid = (1 + 8) / 2 = 4

그러면 공유기를 1번집, 8번집만 설치하게 된다. 설치한 공유기 개수는 2, C(3)보다 작기 때문에 

right를 mid - 1로 설정하고 다시 이분탐색

2. 두 번째 반복

mid = 2일때 1, 4, 8 번 집에 설치하므로 값은 유효함. 일단 result에 기록한 후 더 나은 값이 있는지 살핀다.

더 나은 값이란 제일 인접한 집의 간격이 최대가 되어야하므로 간격을 좀 더 을려봐야한다.

따라서 left = mid + 1 = 3

3. 세 번재 반복

이때에는 1, 4, 9를 설치할 수 있는데 값이 유효하므로 result에 기록

left = mid + 1로 갱신하게되는데 이때 left가 right보다 커지기 때문에 반복문이 종료되고 답은 3.

 

---

풀이 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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);

        int result = 0;
        int left = 1, right = houses[N - 1] - houses[0];

        while (left <= right) {
            int mid = (left + right) / 2;   // 최소 간격 설정.

            // 첫번째 집은 무조건 공유기 설치
            int cnt = 1;
            int lastInstalled = houses[0];  // 마지막으로 설치한 집의 좌표

            // mid를 기준으로 공유기 설치. 첫번째 집은 무조건 설치니깐 1부터 시작
            for (int i = 1; i < N; i++) {
                // 설치하려는 집의 좌표와 이전에 설치한 집의 좌표 간격이 mid보다 클 때 설치
                if (houses[i] - lastInstalled >= mid) {
                    cnt++;
                    lastInstalled = houses[i];
                }
            }

            if (cnt >= C) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(result);


    }
}

 

문제를 점점 어려운걸 풀수록 조건이 복잡해지고 그러다보니 생각을 하다가 까먹는게 있어서

주석을 점점 많이 쓰게 되는 것 같다.

 

그리고 나중에 보다보면 내가 뭐한건지를 모르겠어서 슬슬 메소드로 따로 빼서 구조화를 이쁘게 하는 것도 좋을 것 같다는 생각이 들었다.

쉬운 문제는 뭐 코드가 길지도 않고 조건이 복잡하지도 않으니깐 그냥 쭉 썼는데

앞으로 좀 생각이 비교적 복잡한 문제가 나오면 모듈화를 하는 습관을 길러볼 예정이다.