108 삐약 : 백준 17266 | 어두운 굴다리 [이분 탐색|Binary Search |JAVA]

 

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

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_17266 {
    static int[] lights;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        lights = new int[M];

        //init
        String[] location = br.readLine().split(" ");
        for(int i=0;i<M;i++){
            lights[i] = Integer.parseInt(location[i]);
        }

        //binary search
        int left=1; // 최소 높이
        int right =N; // 최대 높이
        int result =N;

        while(left <= right){
            int mid = (left+right)/2;
            if(isCovered(mid)){
                result =mid;
                right = mid-1;
            }else{
                left = mid+1;
            }

        }
        System.out.println(result);

    }

    static boolean isCovered(int height){
        int lastCovered=0;
        for(int l : lights){
            if(l-height >= lastCovered+1){
                return false;
            }

            lastCovered = l+height;
        }
        return lastCovered >= N;
    }


}

 

 

 

이분 탐색 사용 이유

1. 최적화 문제일 가능성 있음

• "굴다리 전체를 밝히기 위한 가로등의 최소 높이를 구하여라"
• 최소값, 최대값 -> 최적화 문제

 

2. 정답 범위 == 연속적 & 단조 증/감

• 어떤 h에서 모든 구간이 밝혀졌다면, 그보다 큰 높이에서는 항상 가능하다.
• 단조성(단조 증가/감소) 존재

 

3. 탐색 범위

• N <= 10^5
• 이중 반복문 사용 시 10^10 > 10^8 ==1초 -> 시간 초과 발생
• O(log N) 시간복잡도 => 개꿀

 

4. 결정 문제로 바꿀 수 있음

• 가로등 높이가 X일 때 굴다리 전체를 밝힐 수 있는가?(Y/N) 답변이 가능