[백준] 휴게소 세우기 1477 java - 이분탐색

문제를 꼼꼼히 봐야한다!

두가지를 간과해서 계속 틀림,,;;

처음에 left, right 범위를 잘못 잡아줘서 계속 2N%..에서 틀림 ㅜㅜ

'이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다.'

라는 조건 때문에 최소와 최대를 left=1(0이면 x), right=L-1로 잡을 수 있다.

또한 개수를 세는 것이므로 -1을 해줘야 한다

처음에는 (arr[i+1]-arr[i])/mid로 해서 값이 잘 안나왔다 ..

만약 mid=200이라고 하고 arr[1]=200, arr[0]=0이라고 하면

cnt=1이 나오지만 최대값이 mid이므로 1개를 세울 수 없다..!

따라서 (arr[i+1]-arr[i]-1)/mid 로 cnt를 세줘야 한다

 

 

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

 

 

[내 풀이]

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, L;
    static int[] arr;

    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;
            arr[N+1] = L;
            for(int i=1;i<N+1;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(arr);

            int left = 1;
            int right = L-1;

            int answer = 0;
            while(left<=right){
                int mid = (left+right)/2;
                int cnt = 0;

                for(int i=0;i<N+1;i++){
                    cnt += (arr[i+1]-arr[i]-1)/mid;
                }
                if(cnt>M){
                    left = mid+1;
                } else {
                    right = mid-1;
                    answer = mid;
                }
            }

            System.out.println(answer);
    }
}