백준 17266번
https://www.acmicpc.net/problem/17266

문제

---

생각하기

---

• 이분탐색 문제이다.
  • 이분탐색을 통해서 가로등의 최소 높이를 출력하면 된다.
  • 재귀로 구현했다.

동작

    private static int binarySearch(int start, int end) {

        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

        if (check(mid)) {
            end = mid - 1;
            int temp = binarySearch(start, end);

            if (temp == -1) {
                return mid;
            } else {
                return temp;
            }

        } else {
            // mid의 높이로 불가능 할 때,
            start = mid + 1;
            return binarySearch(start, end);
        }

    } // End of binarySearch

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

        for (int i = 0; i < M; i++) {

            if (streetlampArr[i] - height <= prev) {
                prev = streetlampArr[i] + height;
            } else {
                return false;
            }
        }

        return N - prev <= 0;
    } // End of check

가로등을 배열에 저장하고, 이분탐색을 통해서 mid값 찾고 해당 mid높이를 기준으로 가로등의 높이를 check() 메소드를 통해서 정답을 찾는다.

코드

---

Java

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        streetlampArr = new int[M];

        int min = streetlampArr[0];
        int max = streetlampArr[0] + N;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            streetlampArr[i] = Integer.parseInt(st.nextToken());  // 가로등의 위치 X가 주어진다.
        }

        System.out.println( binarySearch(min, max));
    } // End of main

    private static int binarySearch(int start, int end) {

        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

        if (check(mid)) {
            end = mid - 1;
            int temp = binarySearch(start, end);

            if (temp == -1) {
                return mid;
            } else {
                return temp;
            }

        } else {
            // mid의 높이로 불가능 할 때,
            start = mid + 1;
            return binarySearch(start, end);
        }

    } // End of binarySearch

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

        for (int i = 0; i < M; i++) {

            if (streetlampArr[i] - height <= prev) {
                prev = streetlampArr[i] + height;
            } else {
                return false;
            }
        }

        return N - prev <= 0;
    } // End of check
} // End of Main class