[java 백준] 골드 5/ 2110번 공유기 설치

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

2110번: 공유기 설치

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int m;
 
    // 이분탐색으로 받아온 공유기 거리만큼 설치될 수 있는 공유기의 개수
 
    public static int searchWifi(int target, int[] arr) {
        int start = arr[0];
        int cnt = 1;// 우선 첫번째 집에는 공유기 설치할거여서
 
        for (int i = 0; i < n; i++) {
            int end = arr[i];
            if (end - start >= target) {
                cnt++;
                start = arr[i];
            }
        }
        return cnt;// 공유기의 개수 리턴
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = 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 start = 1;// 최소거리
        int end = arr[n - 1] - arr[0] + 1;// 최대거리
 
        // 이분탐색으로 공유기 사이의 거리 조정
        // 찾고자하는 값인 m을 기준으로 인접 공유기간 최대 거리를 구하기
 
        while (start <= end) {
            int mid = (start + end) / 2;
            if (searchWifi(mid, arr) >= m) {
                // target값보다 공유기의 개수가 많을 때
                // 하한선을 올려서 공유기 사이의 거리 늘리기(최대거리 찾기 위함)
                // 하한선을 올리면 mid값이 더 커지면서 공유기 사이 거리가 늘어남
                start = mid + 1;
            } else {
                // target값보다 공유기 개수 적을 때
                // 상한선 내려서 공유기 사이의 거리 줄이기(공유기 개수 m에 맞게 거리 설정)
                // 상한선을 내리면 mid값이 작아지면서 공유기 사이 거리 줄어듦.
 
                end = mid - 1;
            }
 
        }
        System.out.println(end);
 
    }
}

 

공유기 사이의 거리라는 것은 현재 위치의 집에서 바로 그 다음 집까지의 거리를 의미하는 것이다.

내가 문제를 풀면서 간과했던 것은 공유기를 설치한 모든 집간의 거리가 일정해야했다는 것이다.

예를 들어 집 5채가 수직선 위에 있고, 공유기를 3개 설치할거다.

 

내가 공유기 사이 거리가 3이상이여야 한다고 기준을 잡으면

(1,4,8) / (1,4,9) 를 선택할 수 있다.

(1,4,8)의 경우

첫번째 집 1 , 중간 집 4 사이의 거리는 3

중간 집 4, 끝 집 8 사이의 거리는 4 (3 이상)

--> 이렇게 각 집 사이의 거리가 3이상으로 일정해야한다.

 

(1,4,9)의 경우 

첫번째 집 1 , 중간집 4 사이의 거리 3

첫번째 집, 중간집 4 사이의 거리 5 (3이상)

--> 각 집 사이의 거리가 3으로 일정하다.

 

공유기 사이의 거리가 4이상이여야 한다고 기준을 잡으면 

 

(1,8) 만 선택할 수 있다. 

첫번째 집 1에서 거리가 4이상이려면 최소 중간집 위치가 5여야 하는데, 위치가

5인 집이 없으니 8만 온다. 그리고 중간집 8에서 거리가 4이상이려면 최소한 중간집 위치가

12이여야 하는데 집의 위치가 12인 것은 이미 범위를 넘어버렸다.

 

---

그러면 공유기 3대를 설치할 수 있는 모든 경우의 수의 거리를 한번 구해보겠다.

 

최소거리가 1 (2-1)

최대 거리가 9이다.(9-1+1)

그러면 공유기 사이의 거리는 1이상 9이하가 될 수 있다.

 

공유기 사이 거리가 1 이상일 때 (1,2,4,8,9) --> 모든 집에 설치할 수 있지만 그러려면 공유기가 5개 필요하므로 탈락

공유기 사이 거리가 2 이상일 때 (1,4,8),(1,4,9) ,(2,4,8),(2,4,9)

공유기 사이 거리가 3 이상일 때 (1,4,8) ,(1,4,9)

공유기 사이 거리가 4 이상일 때 (1,8)  (2,8) (4,8) --> 모두 2개만 공유기 설치할 수 있기에 탈락

공유기 사이 거리가 5 이상일 때 (1,8) ,(2,8) (4,9)--> 얘네도 2개만 설치할 수 있기에 탈락

공유기 사이의 거리가 6 이상일때 (1,8) (2,8) --> 얘네도 2개만 설치할 수 있기에 탈락

.

.

.

이런식으로 9까지 진행될 것으로 미루어볼 때, 공유기를 3개 설치할 수 있는 집 간의 거리는 2, 3이고 이 중 최대 거리는 3이다. 

 

이것을 구현하기 위해

1. 이분탐색으로 공유기 사이의 거리를 조정할것이다

2. searchWifi 메서드를 통해 공유기 사이의 거리가 n일 때 설치할 수 있는 공유기의 개수를 리턴할 것이다.

 

 

 

int start = 1;// 최소거리

int end = arr[n - 1] - arr[0] + 1;// 최대거리

--> 이분탐색 들어가기 전에 start와 end를 정해준다.

int mid = (start + end) / 2;

 

--> 여기서 mid는 공유기 사이의 일정한 거리를 의미한다. (최소거리+최대거리)/2를 한거니까

 

   if (searchWifi(mid, arr) >= m) {

                start = mid + 1;

    }

 

searchWifi는 공유기의 개수를 리턴해주는 함수인데, 리턴 받은 공유기의 개수가 우리가 설치하고자하는 공유기의 개수 m보다 크거나 같으면 하한선을 올려준다.

하한선을 올려주면 mid값도 커지기 때문에 공유기 간의 거리가 더 커지게 될거다. 그러면 우리가 원하는 인접하는 집 간의 가장 최대의 길이를 구할 수 있을 것이다. 

---

이젠 공유기의 개수를 알려주는 searchWifi 함수를 보자.

 public static int searchWifi(int target, int[] arr) {

        int start = arr[0];

        int cnt = 1;

--> 시작값은 가장 처음에 위치한 집의 위치로 잡고, 얘는 설치한다고 가정하며

공유기의 개수를 뜻하는 cnt변수에 1을 넣어준다.

 

        for (int i = 0; i < n; i++) {

            int end = arr[i];

            if (end - start >= target) {

                 -->현재 위치의 집 - 지금 위치보다 앞에 집 간의 거리가 mid값 즉, 이분탐색을 통해 얻어낸 공유기 사이의

                 거리보다 크거나 같으면

                cnt++;

--> 공유기를 설치해주고

 

                start = arr[i];

--> 현재 위치를 시작점으로 하여 바로 그 다음 집간의 거리를 생각해줄 수 있도록 한다.

            }

        }

        return cnt;// 공유기의 개수 리턴

 

    }

 

---

else {

    end = mid - 1;

}

--> searchWifi를 통해 리턴받은 공유기의 개수가 우리가 찾고자 하는 공유기의 개수(m)보다 작으면

상한선을 내려준다. 그러면 mid값도 내려가니까 공유기 간의 거리가 더 짧아지게 되어서 우리가 원하는

공유기 개수에 인접하게 거리를 설정할 수 있을 것이다.

 

참고자료

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

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

 

풀이 추가 (2022.07.25)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
    public static int n;
    public static int c;
    public static int arr[];
 
 
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        arr=new int[n];
        c=Integer.parseInt(st.nextToken());
 
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(br.readLine());
        }
 
        Arrays.sort(arr);
        //gap을 기준으로 이진탐색
        int start=1;//가장 최소 gap은 1일것
        int end=arr[n-1]-arr[0];
        int ans=0;
 
        while(start<=end){
            int mid=(start+end)/2;
 
            int cnt=1; //cnt 1인것 생각해주기 첫번째 집 방문했다고 가정하고 시작
            int val=arr[0];
            for(int i=1;i<n;i++) {
                if(arr[i]>=val+mid){
                    val=arr[i];
                    cnt++;
                }
            }
 
            if(cnt>=c){
 
                start=mid+1;
                ans=Math.max(ans,mid);
            }
            else{
                end=mid-1;
            }
        }
 
 
 
 
 
        System.out.println(end);
 
 
 
 
 
 
 
 
 
 
 
 
    }
 
}