[백준] 17266: 어두운 굴다리 - JAVA

in Algorithm on 기타

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

풀이

가로등의 높이를 조정하여 길을 모두 비추도록 하는 문제였다.

따라서 가로등의 높이를 기준으로 이분탐색을 진행했다.

이분탐색의 mid값을 현재 체크할 높이로 하여 check메서드를 수행했고,

마지막 지점까지 비추는 것을 확인하기 위해 return prev >= N으로 처리했다.

메모리: 25084KB

시간: 316ms

언어: Java 11

코드

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        arr = new int[M];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 1;
        int right = N;
        while (left < right) {
            int mid = (left + right) / 2;

            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(left);
    }

    private static boolean check(int mid) {
        int prev = 0;

        for (int i = 0; i < M; i++) {
            if (arr[i] - mid <= prev) {
                prev = arr[i] + mid;
            } else {
                return false;
            }
        }

        return prev >= N;
    }

}