백준 2110 - 공유기 설치(자바 - 이진 탐색)

백준 2110 - 공유기 설치(자바 - 이진 탐색)

중량 제한 문제와 같이 이진 탐색을 통해 해결 할 수 있는 문제

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

이 문제 또한 공유기 설치 때와 같이 이진 탐색을 어떻게 수행해야 하는지 감이 잡히지 않았으므로 패스트 캠퍼스 코딩테스트 문제 해설 강의를 참고했다.

입력 받은 좌표간의 최소 격차, 최대 격차를 각각 start, end 로 잡고 이진 탐색을 수행한다.

- 입력 받은 좌표간의 최소 격차, 최대 격차를 각각 start, end 로 잡고 이진 탐색을 수행해서 해결하는 문제이다.

- 매 반복마다 middle 값을 구한 후 해당 값으로 입력 받은 갯수만큼 공유기 설치가 가능한지 판별한다.

- middle 값으로 지정된 격차 와 같거나 더 크게 떨어져 있는 좌표 들 간에만 공유기 설치가 가능하다.

- 가능한 최대 격차를 구하는데 있어서 입력받은 설치 갯수보다 더 많이 설치 할 수 있으면 격차가 더 커야 하므로

일단 결과 변수에 middle 값을 저장해주고 난 다음, start 를 middle + 1 로 지정해서 범위를 격차가 더 큰 쪽으로 좁혀준다.

- 입력받은 설치 갯수보다 더 적게 설치 할 수 있으면 격차가 더 작아야 하므로 end 를 middle - 1 로 지정해서 범위를 격차가 더 작은 쪽으로 좁혀준다.

- 반복문이 끝나면 최종적으로 입력받은 설치 갯수를 기준으로 설치 가능한 최대 격차 값을 구할 수 있게된다.

- Main.java

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { // 가장 인접한 두 공유기 사이의 최대 Gap 을 이진 탐색으로 찾는다. // 반복적으로 Gap 을 설정하며, C 개 이상의 공유기를 설치할 수 있는 경우를 찾는다. // 1,2,3,8,9 인 경우 최대 Gap : 8, 최소 Gap : 1 // 최소 gap 과 최대 gap 을 min, max 로 설정한 다음 그 중간값을 반복적으로 찾으면서 // 그 와 동시에 min, max 값을 조건에 맞게 갱신해주는 방식으로 가능한 최대 Gap 을 찾는다. // 설치 가능한 공유기의 수가 C 보다 작으면 Gap 을 감소시키고, C 보다 많으면 Gap 을 증가시킨다. // 처음으로 C 개의 공유기 설치가 가능한 gap 을 찾았을 경우, 일단 해당 gap 을 결과로 저장한다음 // gap 의 값을 1씩 증가시키면서 최대로 가능한 gap 값을 찾는다. BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int arraySize = Integer.parseInt(st.nextToken()); int router = Integer.parseInt(st.nextToken()); int[] home = new int[arraySize]; for(int i = 0; i < home.length; i++) { home[i] = Integer.parseInt(br.readLine()); } Arrays.sort(home); int maxGap = home[home.length-1] - home[0]; int minGap = 1; int start = minGap; int end = maxGap; int middle = (start + end) / 2; int result = 0; while(start <= end) { int count = 1; int standard = home[0]; middle = (start + end) / 2; for(int i = 1; i < home.length; i++) { if(home[i] - standard >= middle) { standard = home[i]; count++; } } if(count >= router) { start = middle + 1; result = middle; } else { end = middle - 1; } } bw.write(result + "

"); bw.flush(); bw.close(); } }

from http://evan-development.tistory.com/150 by ccl(A) rewrite - 2021-12-21 22:01:33