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

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;
    }

}