[백준] 공유기 설치 2110번 - java

문제 2110번

문제는 다음과 같다.

우리가 아는 정보는 우선 집의 개수 N, 공유기의 개수 C, 집의 좌표다

우리가 구해야 할 것은 가장 인접한 두 공유기의 최대 거리다.

아이디어

하나하나 비교해보며 공유기 위치를 찾기는 매우 비효율적이고, 시간도 오래 걸릴 것이다.

가능한 공유기 범위를 구하고, 그 범위의 절반부터 시작해 "이진 탐색"을 하는 것이 나을 것 같다.

입력받은 집의 좌표를 오름차순 정렬하는 것도 필요하다.

우선 가장 쉽게 입력부터 코드를 짜보자.

package test;

import java.util.Arrays;
import java.util.Scanner;

public class main {
	
	static int address[];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
        // 집의 수 
		int n = sc.nextInt();
        
        // 공유기의 수 
		int m = sc.nextInt();
        
        
		// 집의 좌표
		address = new int[n];
		
		for(int i=0; i<n; i++) {
			address[i] = sc.nextInt();
		}
		
        // 입력 받은 집의 좌표 정렬해주기
		Arrays.sort(address);

	}

}

코드 흐름

이제 이진탐색 해주는 메소드를 짜보자.
코드의 흐름은 다음과 같다.

1. 입력 받기

2. 탐색 구간 설정

• 가능한 공유기 간격의 범위를 low ~ high
• 이때 low는 1부터 시작한다.
• high는 가장 먼 두 집 사이의 거리이기에 address[n-1] - address[0]이다.

3. 이진 탐색 반복

• 중간값 distance를 기준으로 이 거리로 공유기 c개를 다 설치할 수 있는지 확인한다.

4. 설치 가능 여부에 따라 간격 조정하기

• 가능하다면 간격을 늘려본다. low = distace +1
• 불가능하다면 간격을 줄여본다. high = distance-1

5. 가능했던 거리 가장 큰 값을 출력하기

메소드 짜보기

//거리 탐색 
	static void method(int n, int c) {
		//최소 간격 
		int low = 1;
		
		
		//최대 간격 (양 끝 집 거리) 
		int high = address[n-1] - address[0];
		
		int ans = 0;
		
		while(low<=high) {
			int distance = (low + high)/2;
			
			int cnt=1;
			int last = address[0];
			
			for(int i=1; i<n; i++) {

				if(address[i]-last >= distance) {
					cnt++;
					last = address[i];
				} 
			}
			if(cnt >=c) {
				ans = distance;
				low = distance +1;
			} else {
				high = distance-1;
			}
		}
		
		System.out.println(ans);
	
	}

이렇게 하면 문제를 해결할 수 있다!