[백준]1477: 휴게소 세우기 - JAVA

[백준]1477: 휴게소 세우기

풀이

딱 보자마자 이분탐색을 통해 풀어야 겠다는 생각이 들지 않았어서 풀이하는데 시간이 좀 걸렸다. 이분탐색 유형에 아직 익숙하지 않아서 그런 것 같다.

 

이 문제는 휴게소의 간격을 기준으로 이분탐색을 진행한 다음 해당 간격이 형성되도록 M개의 휴게소를 생성할 수 있을 때의 최소값을 찾는 문제이다.

 

예제 입력1을 예시로 살펴보자. 휴게소가 설치될 수 있는구간은 다음과 같다.

1 ~ 81

83 ~ 200

202 ~ 410

412 ~ 554

556 ~ 621

623 ~ 754

756 ~ 799

 

휴게소의 위치와 0, L을 포함한 값을 배열에 담아 정렬시켜준다. (범위 값 계산을 하기 위해)

이때, 휴게소 간격의 최소값은 0, 최대값은 L이 된다.

 

이제 이분 탐색을 시작한다. 탐색하며 찾는 값은 휴게소 간격이 되며 mid값으로 설정한다.

can_make 함수에서 휴게소 간격을 mid로 설정했을때, 몇 개의 휴게소를 설치할 수 있는지 count하고 설치해야 하는 휴게소 개수인 M개보다 크다면 큰 범위를, 작다면 작은 범위를 이분 탐색한다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n, m, l;
    static ArrayList<Integer> list;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        l = scan.nextInt();
 
        list = new ArrayList<>();
        list.add(0); //제일 작은 값
        list.add(l); //제일 큰 값
        for(int i = 0; i < n; i++) {
            list.add(scan.nextInt());
        }
        Collections.sort(list);
        
        int left = 0;
        int right = l;
        while(left <= right) {
            int mid = (left + right) / 2; //휴게소의 간격
            if(can_make(mid)) left = mid + 1;
            else right = mid - 1;
        }
        System.out.println(left);
    }
 
    public static boolean can_make(int mid) {
        int count = 0;
        for(int i = 1; i < list.size(); i++) {
            count += (list.get(i) - list.get(i - 1) - 1) / mid;
        }
        if(count > m) return true;
        return false;
    }
}