백즌 17266 java : 구현, 이진탐색

왜 이진탐색을 사용했는가?

브루트포스로는 풀이가 쉽겠지만, 소모시간이 문제 조건을 충족하지 못할 것이라 생각했다. 이진 탐색으로 최대높이인 N부터 시작해 이진탐색으로 최소높이를 찾는다.

import java.util.Scanner;

public class bj17366 {
    static Scanner sc = new Scanner(System.in);
    static int N, M;
    static int [] location;

    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        sc.close();
    }

    public static void inputData(){
        int i;

        N = sc.nextInt();
        M = sc.nextInt();
        location = new int[M];

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

    public static int findAnswer() {
        int left = 0, right = N, answer = N, mid;

        //이진 탐색
        while (left <= right) {
            mid = (left + right) / 2;
            if (lightTunnel(mid)) {
                answer = mid;
                right = mid - 1;
                System.out.println("right 이동");
            } else {
                left = mid + 1;
                System.out.println("left 이동");
            }
        }

        return answer;
    }

    public static boolean lightTunnel(int H) {
        int i;
        int covered = 0;
        int left, right;


        System.out.println("H : " + H + "일 때");
        for (i = 0; i < M; i++) {
            left = location[i] - H;
            right = location[i] + H;

            //빛이 0(시작점)을 밝히지 못함
            if (left > covered) {
                System.out.println("시작위치 덮지 못함");
                return false;
            }

            covered = Math.max(covered, right);
            System.out.println("covered : " + covered);

            //전부 다 덮음
            if (covered >= N) {
                break;
            }
        }

        if(covered >= N){
            System.out.println("전부 다 덮음");
            return true;
        }
        else{
            System.out.println("전부 다 덮지 못함");
            return false;
        }
    }
}