백준#1477 휴게소 세우기 (java)

전체 코드

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

public class Main {
    public static void main(String[] args) {
        new Sol();
    }
}
class Sol{
    int N, M, L;
    private final Buf buf = new Buf();
    int[] input;
    public Sol(){
        N = buf.readInt();
        M = buf.readInt();
        L = buf.readInt();
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i<N; i++){
            q.add(buf.readInt());
        }
        int tmp = 0;
        input = new int[N+1];
        for (int i = 0; i<N+1; i++){
            if (i==N){
                input[N] = L-tmp;
            }else{
                int poll = q.poll();
                input[i] = poll - tmp;
                tmp = poll;
            }
        }
        int right = L;
        int left = 1;

        while(left<=right){
            int mid = (right+left)/2;
            if (isCan((mid))){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        System.out.println(left);
    }
    public boolean isCan(int mid){
        int idx = 0;
        for (int i = 0; i<=N; i++){
            idx+=(input[i]/mid);
            if (input[i]%mid==0)idx--;
        }
        return M<idx;
    }
}
class Buf{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    public String read(){
        while(st==null||!st.hasMoreElements()){
            try{
                st = new StringTokenizer(br.readLine());
            }catch(IOException e){
                return null;
            }
        }
        return st.nextToken();
    }
    public Integer readInt(){
        return Integer.parseInt(read());
    }

    public Long readLong(){
        return Long.parseLong(read());
    }
}

풀이

 

각 구간별로 나눠보면 (구간 최대값)이 들어갈 수 있는 위치가 M개 이상 나와야하며 그 값의 최솟값을 구하는 문제이다. 즉 구간 최대값을 사용해서 매개변수 탐색하면 된다.

 

PriorityQueue<Integer> q = new PriorityQueue<>();
for (int i = 0; i<N; i++){
    q.add(buf.readInt());
}

정렬해줘야하니 우선순위 큐에 입력값을 넣어준다.

int tmp = 0;
input = new int[N+1];
for (int i = 0; i<N+1; i++){
    if (i==N){
        input[N] = L-tmp;
    }else{
        int poll = q.poll();
        input[i] = poll - tmp;
        tmp = poll;
    }
}

각 구간의 길이를 넣어준다.

int right = L;
int left = 1;

while(left<=right){
    int mid = (right+left)/2;
    if (isCan((mid))){
        left = mid+1;
    }else{
        right = mid-1;
    }
}

`isCan` 에 따라 이진 탐색을 진행한다.

public boolean isCan(int mid){
    int idx = 0;
    for (int i = 0; i<=N; i++){
        idx+=(input[i]/mid);
        if (input[i]%mid==0)idx--;
    }
    return M<idx;
}

만약 현재 최대 구간이 구간의 길이와 나누어 떨어진다면 휴게소가 곂치게 된다. 따라서 해당 부분은 1 감소시켜준다.