[BOJ][JAVA] 어두운 굴다리 17266

문제

문제(출처: https://www.acmicpc.net/problem/17266)

입/출력

입출력(출처: https://www.acmicpc.net/problem/17266)

풀이(바로 보기 쉽게 설명은 주석으로 달았습니다)

package binary_search;

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

/**
 * [ Precondition ]
 * - It can as shine as the height of the street light.
 * - is Integer
 * - height is equal
 *
 * [ Input ]
 * Line 1 - 굴다리 N (1~100,000)
 * Line 2 - 가로등 개수 M (1~N)
 * Line 3 - 설치할 수 있는 가로등 위치 X (오름차순으로 입력, 중복X, 정수)
 *
 * [ Output ]
 * 굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이 출력
 */
public class 어두운굴다리17266 {



    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int result = 0; // 최소 높이

        int N = Integer.parseInt(reader.readLine().trim()); // 굴다리 길이
        int M = Integer.parseInt(reader.readLine().trim()); // 가로등 개수
        int[] x = new int[M]; // 가로등의 좌표 x

        StringTokenizer st = new StringTokenizer(reader.readLine());
        for(int i = 0; i < M; i++) {
            int coordinate = Integer.parseInt(st.nextToken());
            x[i] = coordinate;
        }

        result = getMinimunLength(x, N);

        System.out.println(result);
    }

    private static int getMinimunLength(int[] x, int N) {
        int low = 1; // 최소 높이(= N이 1일 떄)
        int high = N; // 최대 높이(= M이 1일 떄)
        int res = 0; // 응답할 값(= 찾은 최소 높이)

        while (low <=high) {
            int mid = (low+high)/2; // 가로등 높이
            boolean flag = true;

            // mid 높이로도 굴다리를 모두 비출 수 있는지 확인
            int lastIlluminated = 0; // 현재까지 가로등이 비춘 가장 오른쪽 지점
            for(int i = 0; i < x.length; i++) {
                if(x[i] - mid <= lastIlluminated) { // i번째 가로등이 중간보다 왼쪽에 있으면
                    lastIlluminated = x[i] + mid; // i좌표로부터 비출 수 있는 거리로 업데이트
                } else {
                    flag = false; // 모두 비출 수 없음
                }
            }
            // 마지막 지점의 가로등이 비춘 곳과 굴다리의 끝지점을 확인
            if (N - lastIlluminated > 0) // 이 시점의 lastIlluminated는 마지막으로 비춰진 곳(굴다리를 모두 비췄다면 N - lastIlluminated는 0보다 같거나 작아야 함)
                flag = false; // 모두 비출 수 없음
            else flag = true;

            if (flag) { // 모두를 비출 수 있음
                res = mid; // mid를 일단 최소 높이라고 가정하고
                high = mid - 1; // high를 mid보다 작은 값으로 셋팅한 후, 다음 단계로 일단 진행
            } else { // 모두 비출 수 없음
                low = mid + 1; // 다음 단계로
            }
        }

        return res;
    }
}