[백준] 2110 공유기 설치 - 파라매트릭 서치(Paramatric Search) JAVA

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

2110번: 공유기 설치

코드설명

파라매트릭 서치 문제입니다.

 

문제로직은, 

1. 공유기의 최소거리(start)와 최대거리(end)를 구합니다. 

2. 파라매트릭 서치를 위하여 middle 값( ( start + end ) / 2)를  구합니다.

3. 공유기의 첫 시작 위치를 정하고, 각 공유기간의 거리와 middle 값을 비교하여, 공유기 간의 거리가 middle 값보다크다면, 설치가 가능하므로 설치하고, 새로 설치한 위치로 시작위치를 재설정합니다. 그리고 공유기의 개수를 1 증가시킵니다.

4. middle 값보다 작다면 설치가 불가능하므로 공유기 간의 거리를 증가시킵니다. 

5. cnt보다 C가 크다면, 각 공유기 간의 거리를 최대화 시키기 위해, 거리를 증가시키는 start = middle + 1 처리를 합니다. 해당 작업을 통해 cnt를 감소시키며, cnt가 C와 최대한 가깝게 설정하게 됩니다.

 

6. 2~5번의 과정을 반복합니다.

 

우리가 구하고자하는것은 두 공유기 사이의 최대 거리입니다. 그러므로, 가장 인접한 두 공유기 사이의 거리를 조절해가며 공유기를 설치하다, C만큼 공유기를 설치할 수 있으면서 최대거리를 구하는 로직을 구하면됩니다.

위의 로직을 통해 해결할 수 있습니다. 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, C;
	public static int[] arr;
	public static long start = 0, end = 0;
	public static long answer = 0;
    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());
    	C = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	
    	paraMatricSearch();
    	System.out.println(answer);
    }
    
    public static void paraMatricSearch() {
    	start = 0; //공유기 설치 최소 거리
    	end = arr[N-1] - arr[0]; //공유기 설치 최대거리
    	
    	while(start <= end) { //공유기 설치 최소거리가 공유기 설치최대거리보다 작거나 같을동안만 작동
    		long middle = (start + end) / 2; // (공유기 설치최소 거리 / 공유기 설치 최대거리) / 2 = 공유기 설치 중간 거리, 이분탐색으로 진행하여 O(log N)의 시간으로 단축
    		
    		long startHomeValue = arr[0]; // 공유기거리 비교를 위한 공유기 시작 위치를 저장
    		long distance = 0;   //공유기 간의 거리 변수
    		long cnt = 1; //공유기 설치 개수, 첫번째 위치는 설치하고시작
    		for(int i=0;i<N;i++) {
    			distance = arr[i] - startHomeValue; //공유기 간의 거리 검사
    			
    			if(distance >= middle) { //거리보다 middle(공유기 설치면적)이 작다면, 설치가가능, middle 거리부터 측정
    				startHomeValue = arr[i]; //설치했으니, 해당 위치가 시작위치로 변화
    				cnt += 1; //공유기 설치
    			}
    		}
    		
    		if(cnt >= C) { //만약 설치공유기 개수가 C보다 크다면, 공유기거리를 증가시켜서 최대 공유기거리를 구하도록 설정
    			start = middle + 1;
    			answer = middle;
    		}else { //만약 설치공유기 개수가 C보다 작다면, 공유기거리를 감소시켜서 최대 공유기거리를 구하도록 설정
    			end = middle - 1;
    		}
    		
    		
    	}
    	
    }
    
}

 

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, C;
	public static int[] arr;
	public static int answer0=0, answer1=0;
    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());
    	C = Integer.parseInt(st.nextToken());
    	
    	int end = 0;
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
    	
    	Arrays.sort(arr);
    	paramatricSearch(0, end);
    }
    
    public static void paramatricSearch(int start, int end) {
    	long left = 0; //최소거리
    	long right = end; //최대거리(0 ~ 최대값이 최대거리가 될 것이다.)
    	
    	while(left <= right) {
    		long middle = (left + right) / 2; //최소 공유기 거리. 이 공유기 거리는 무조건 이상이여야합니다.
    		
    		
    		long startHomeValue = arr[0]; //공유기 시작 위치를 한개 저장하고 시작합니다.
    		long distance = 0; //공유기 간의 거리 변수.
    		long sum = 1; //공유기 설치개수, 첫번째 위치는 설치하고 시작.
    		//공유기 C개를 설치해보자.
    		for(int i=0;i<N;i++) {
    			distance = arr[i] - startHomeValue; //공유기 간의 거리를 검사합니다.
    			if(distance >= middle) { //문제에서 구하고자하는 것은 두 공유기 사이의 최대거리를 구하고자하므로, middle 값보다 크다면 설치가능합니다.  
    				startHomeValue = arr[i];
    				sum += 1;
    			}
    		}
    		
 
    		if(sum >= C) {
    			left = middle + 1;
    		}else {
    			right = middle - 1;
    		}
    	}
    	System.out.println(right);
    	
    }
    
}