[백준] 1477 휴게소 세우기 - 파라매트릭 서치(Paramatric Search) JAVA

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

1477번: 휴게소 세우기

코드설명

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

 

휴게소 간의 거리를 파라매트릭 매개변수로 설정하고, 

기존 휴게소들 간의 거리를 매개변수와 비교하며 진행합니다.

 

문제전체 로직을 간단하게 설명해보면,

추가로 휴게소 M개를 설치하면서, 휴게소 간 최소거리를 찾기 위해 각 거리별로 추가설치할 수 있는 휴게소를 설치해가며, M개보다 많이 설치한다면, 휴게소 간 거리를 증가시켜서 휴게소를 적게 설치하고, M개보다 적거나 같게 설치한다면, 휴게소 간 거리를 감소시켜먼서 최적의 휴게소 거리를 찾아갑니다.

 

문제에서 유의해야할 점들은,

for(int i=0;i<N+1;i++) { 
    int dist = ( arr[i+1] - arr[i]); //기존 휴게소 간 거리 구하기
    cnt += dist / middle; //휴게소 설치

    if( dist % middle == 0) //값이 완전히 나눠지면 2개의 휴게소가 설치되는 공간에 3개의 휴게소가 설치되므로 -1 해야합니다.
        cnt--;
}


혹은

for(int i=0;i<N+1;i++) { 
    int dist = ( arr[i+1] - arr[i] - 1); //기존 휴게소 간 거리 구하기
    cnt += dist / middle; //휴게소 설치
}

• 값이 완전히 나눠지면 2개의 휴게소가 설치되는 공간에 3개의 휴게소가 설치되므로 해당 로직을 추가해줘야합니다.

 

또한, 설치한 휴게소의 개수 (cnt) 가 설치하려고하는 M개보다 크거나 같은 경우라고 생각했지만, 큰 경우에 start = middle + 1 처리를 합니다. 위의 이유에 대해서는 명확하게 이해하지는 못했습니다.

일반적으로는 cnt >= M 으로 처리하여, 크거나 같은경우에서 계속해서 최적의 값을 찾아가는데, 해당 문제의 경우 

[휴게소가 없는 구간의 최댓값의 최솟값을 출력한다. ] 이러한 조건때문에 그런것이라고 짐작하지만 일단은 명확한 이유에 대해서는 깨닫지 못했습니다. 

if(cnt > M) { //더 지으려고하는 휴게소의 개수 M보다 더 많이 지었다면, 거리를 증가시켜서 줄여야됩니다.
    start = middle + 1;
}else { //더 지으려고하는 휴게소의 개수 M보다 같거나 더 작게 지었다면, 거리를 감소시켜서 더 지어야합니다. 
    end = middle - 1;
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M, L;
	public static int[] arr;
	public static int start = 0, end = 0;
	public static int 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());
    	M = Integer.parseInt(st.nextToken());
    	L = Integer.parseInt(st.nextToken());
    	arr = new int[N+2];
    	
    	st = new StringTokenizer(br.readLine());
    	arr[0] = 0; // 처음 휴게소 위치 0
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	arr[N+1] = L; //마지막 휴게소 위치 L
    	Arrays.sort(arr);
    	
    	paramatricSearch();
    }
    
    public static void paramatricSearch() {
    	start = 1; //시작점은 포함안됨
    	end = L-1; //끝점은 포함안됨
    	
    	while(start <= end) {
    		int middle = (start + end) / 2; //중간길이부터 검사
    		
    		int cnt = 0;
    		for(int i=0;i<N+1;i++) { 
    			int dist = ( arr[i+1] - arr[i] - 1); //기존 휴게소 간 거리 구하기
    			cnt += dist / middle; //휴게소 설치
    			
//    			if( dist % middle == 0) //값이 완전히 나눠지면 2개의 휴게소가 설치되는 공간에 3개의 휴게소가 설치되므로 -1 해야합니다.
//    				cnt--;
    		}
    		
    		if(cnt > M) { //더 지으려고하는 휴게소의 개수 M보다 더 많이 지었다면, 거리를 증가시켜서 줄여야됩니다.
    			start = middle + 1;
    		}else { //더 지으려고하는 휴게소의 개수 M보다 같거나 더 작게 지었다면, 거리를 감소시켜서 더 지어야합니다. 
    			end = middle - 1;
    		}
    	}
    	System.out.println(end + 1); 
    }
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M, L;
	public static int[] arr;
	public static int start = 0, end = 0;
	public static int 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());
    	M = Integer.parseInt(st.nextToken());
    	L = Integer.parseInt(st.nextToken());
    	arr = new int[N+2];
    	
    	st = new StringTokenizer(br.readLine());
    	arr[0] = 0; // 처음 휴게소 위치 0
    	for(int i=1;i<=N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	arr[N+1] = L; //마지막 휴게소 위치 L
    	Arrays.sort(arr);
    	
    	paramatricSearch();
    }
    
    public static void paramatricSearch() {
    	start = 1; //시작점은 포함안됨
    	end = L-1; //끝점은 포함안됨
    	
    	while(start <= end) {
    		int middle = (start + end) / 2; //중간길이부터 검사
    		
    		int cnt = 0;
    		for(int i=0;i<N+1;i++) { 
    			int dist = ( arr[i+1] - arr[i]); //기존 휴게소 간 거리 구하기
    			cnt += dist / middle; //휴게소 설치
    			
    			if( dist % middle == 0) //값이 완전히 나눠지면 2개의 휴게소가 설치되는 공간에 3개의 휴게소가 설치되므로 -1 해야합니다.
    				cnt--;
    		}
    		
    		if(cnt > M) { //더 지으려고하는 휴게소의 개수 M보다 더 많이 지었다면, 거리를 증가시켜서 줄여야됩니다.
    			start = middle + 1;
    		}else { //더 지으려고하는 휴게소의 개수 M보다 같거나 더 작게 지었다면, 거리를 감소시켜서 더 지어야합니다. 
    			end = middle - 1;
    		}
    	}
    	System.out.println(start); 
    }
    
}