[백준] 17266번 어두운굴다리 java

문제 링크 : https://www.acmicpc.net/problem/17266

1. 백준 17266번 문제

1. 문제

2. 입력

첫 번째 줄에 굴다리의 길이 N 이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 가로등의 개수 M 이 주어진다. (1 ≤ M ≤ N)

다음 줄에 M 개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 ≤ x ≤ N)

가로등의 위치 x는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

3. 출력

굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이를 출력한다.

2. 문제 해석

높이 만큼 양쪽으로 불을 밝히는 가로등이 있습니다. 주어진 도로 길이를 위 가로등으로 밝히는 문제입니다.

3. 문제 풀이

import java.util.Scanner;

public class Main {
    static int[] Arr;
    static int N,M;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        N =sc.nextInt(); //굴다리의 길이
        M =sc.nextInt(); //설치할 가로수 갯수.
        Arr = new int[M];// 가로등이 설치된 지점 입력 받기

        for(int i = 0; i < M; i++) {
            Arr[i] = sc.nextInt();
        }

        int left = 1;
        int right = N;
        int result = 0;

        while(left <= right) {
            int mid = (left + right) / 2;
            // mid 높이로 모든 지점을 비출 수 있다면 result 갱신 후 높이를 줄여 재탐색
            if(possible(mid)) {
                result = mid;
                right = mid - 1;
            }
            // 모든 지점을 비출 수 없다면 높이를 높여 재탐색
            else
                left = mid + 1;
        }
        System.out.println(result);
    }

    static boolean possible(int target) {
        int prev = 0; // 이전 가로등이 비춘 마지막 지점, 0 지점부터 모두 비춰주어야 하기 때문에 0부터 시작

        for(int i = 0; i < Arr.length; i++) {
            /*
             * 가로등이 있는 지점에서 비출 수 있는 높이(target)을 빼면 가로등이 비추는 최소값을 알 수가 있습니다.
             * 이 최소값을 기준으로 가로등이 빈곳없이 다 비추는지 조건을 확인합니다.
             */
            if(Arr[i] - target <= prev) {
                prev = Arr[i] + target;
                // Arr[i] + target을 하게되면 가로등이 다시 비춰야만 하는 최소값을 리턴할 수 있습니다.
            } else { return false; }
            /*
             * 가로등의 시작 지점에서 높이(target)만큼 비춘 곳이
             * 이전 가로등이 마지막으로 비춘 곳에 도달하지 못하면 모든 지점을 비출수 없습니다.
             */
        }
        /*
         * 마지막 지점도 가로등이 비출 수 있는지 확인해야 하기 때문에
         * 마지막 가로등이 비출 수 있는 끝 지점에서 굴다리의 끝 좌표를 뺐을 때 0보다 작거나 같아야 마지막 지점도 비춰집니다.
         */
        return N - prev <= 0;
    }
}