백준 2110 용돈 관리 (JAVA 자바 풀이)

백준 2110 용돈 관리 (JAVA 자바 풀이)

 

 

 

---

 

 

 

문제

 

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

 

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

 

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

---

 

 

💡 풀이 과정

 

 

파라미트릭 바이너리 서치를 이용해서 푸는 문제인데, 기존의 문제들보다 조금 난이도가 높았다. 풀이 아이디어는 결국 비슷한데, 주어진 자료보다 한단계 더 생각할 수 있는지 여부를 보는 것 같이 느껴졌다. 또 decistion 함수 구현에 있어서도 단순 brute 방법이 아니라 효율적인 접근을 생각해낼 수 있는지도 중요했던 것 같다. 

 

유형 자체는 대표적인 유형이라고 한다. "가장 먼 ~", "가장 가까운 ~"과 같은 표현이 나오면 파라미트릭 서치를 생각해볼 수 있다. 

 

다음과 같은 예를 들어보자. 

 

5 4

5

14

16

19

20 

 

정답은 2이다. 

 

5 - 14 - 16 - 19 - 20 중에 5, 14, 16, 20을 선택한다고 하면 

각각 거리는 9, 2, 4 이므로 2가 나온다. 

 

5 - 14 - 16 -19 -20 중에 5, 14, 16, 19를 선택하면 

각각 거리는 9, 2, 3이므로 마찬가지로 2이다. 

 

3 이상이 될 수는 없을까? 

 

3이상의 거리를 유지하면서 배치를 해보면 4개를 전부 배치할 수 없다. 

 

5, 14, 19를 설치하면 3씩 배치할 수 있지만 하나가 남게 된다. 

 

즉 이와 같은 시도를 통해 알 수 있는 것은 특정 거리를 유지하면서 설치를 했을 때 요구사항에 주어진 공유기를 모두 설치할 수 있는가를 판단해야 한다는 것이다. 

즉, 인접한 거리를 지키면서 최대한 설치할 수 있는지를 판단하는 결정함수가 이 문제 풀이의 핵심이 될 것이다. 

 

다음과 같이 구현할 수 있다. 

 

private static boolean canPlaceRouter(int[] houses, int routerCounts, int distance) {
   int count = 1;
   int lastInstall = houses[0];

   for (int house : houses) {
      if (house - lastInstall >= distance) {
         count++;
         lastInstall = house;
      }
   }

   return count >= routerCounts;
}

 

코드를 살펴보면 canPlaceRouter 함수는 주어진 거리를 유지하며 공유기를 설치할 수 있는지 여부를 판단한다. 이 경우, "특정 거리를 유지하며 모든 공유기를 설치할 수 있는가?"라는 결정 문제로에 대한 판단 결과를 리턴한다 

 

이제 이 함수를 사용하여 실제로 공유기를 설치할 수 있는 최대 거리를 찾는 바이너리 서치를 구현하려면 다음과 같은 정의가 필요하다.

 

만약 결정 함수가 답이 될 수 있음을 리턴한다면 값을 키워야 한다 

만약 결정 함수가 답이 될 수 없음을 리턴한다면 값을 내려야 한다. 

 

초기화 값은 어떻게 정할까?

 

가능한 최소거리와 최대 거리를 l과 r로 설정하면 될 것이다.

최소 거리는 1이다. 최대 거리는 가장 작은 값과 가장 큰 값의 차이이다. 

 

int l = 1; // 최소 거리
int r = houses[houseCounts - 1] - houses[0]; // 최대 거리
int answer = 0;

 

 

canPlaceRouter 함수를 사용하여 중간 값에서 공유기를 설치할 수 있는지 확인합니다.
   - 만약 설치할 수 있다면, l를 m + 1로 설정하여  공유기 사이의 거리를 늘린다.
   - 설치할 수 없다면, r를 m - 1로 설정하여 공유기 사이의 거리를 좁힌다. 

 

이를 코드로 구현해보면 다음과 같다. 

 

while (l <= r) {
   int m = (l + r) / 2; // 중간 거리
   if (canPlaceRouter(houses, routerCounts, m)) {
      answer = m;
      l = m + 1;
   } else {
      r = m - 1;
   }
}

 

 

 

시간 복잡도를 계산해보자. 

 

sort에서 (NlogN)이고  

결정함수에서 O(n), 바이너리 서치에서 O(logX)이므로 

각각 최대 시간 복잡도는 O(NlogX) 이다. 

 

 

💡 코드 구현

import static java.lang.Integer.*;
import static java.util.Arrays.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

   public static void main(String[] args) throws IOException {

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int houseCounts = parseInt(stringTokenizer.nextToken());
      int routerCounts = parseInt(stringTokenizer.nextToken());

      int[] houses = new int[houseCounts];
      for (int i = 0; i < houseCounts; i++) {
         stringTokenizer = new StringTokenizer(bufferedReader.readLine());
         houses[i] = parseInt(stringTokenizer.nextToken());
      }

      sort(houses);    // nlogn

      int l = 1; // 최소 거리
      int r = houses[houseCounts - 1] - houses[0]; // 최대 거리
      int answer = 0;

      while (l <= r) {
         int m = (l + r) / 2; // 중간 거리
         if (canPlaceRouter(houses, routerCounts, m)) {
            answer = m;
            l = m + 1;
         } else {
            r = m - 1;
         }
      }
      System.out.println(answer);
   }


   private static boolean canPlaceRouter(int[] houses, int routerCounts, int distance) {
      int count = 1;
      int lastInstall = houses[0];

      for (int house : houses) {
         if (house - lastInstall >= distance) {
            count++;
            lastInstall = house;
         }
      }

      return count >= routerCounts;
   }



}