[자바로 푸는 백준] 17266번 어두운 굴다리

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

17266번: 어두운 굴다리

✅실버 Ⅳ

 

🔶 풀이

굴다리 길이(N)와 가로등 개수(M), 가로등 설치 위치가 주어지고, 굴다리의 모든 곳을 비추어라.

가로등 높이가 1 증가할 때마다 길이 1만큼 더 주위를 비출 수 있다.

 

이분 탐색을 이용해서 가로등의 적정 높이를 찾아주면 된다.

가로등의 높이를 기준으로 굴다리의 모든 곳을 비출 수 있는지 확인하면서 가능하다면 최댓값(right)를 mid-1로, 불가능하다면 최솟값(left)를 mid+1로 변경하면서 진행한다.

 

public static boolean canLight(int h) {
    int prev = 0; // 이전 가로등이 비춘 위치
		
    for (int i=0; i<streetlamp.length; i++) {
        if (streetlamp[i] - h <= prev) {
            prev = streetlamp[i] + h;
        } else {
            return false;
        }
    }
		
    // 마지막 가로등이 비추는 곳이 굴다리 길이보다 같거나 커야함
    return N - prev <= 0;
}

가로등이 설치된 위치에서 가로등의 높이를 빼주면 해당 가로등이 비추는 최소 위치를 알 수 있다. 최소 위치가 이전 가로등이 비춘 최대 위치보다 적거나 같다면 빈 곳없이 비추고 있다는 의미다.

 

또한, 마지막 가로등이 비추는 최대 위치가 굴다리 길이보다 크거나 같아야한다. 

 

 

<최종코드>

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

public class Main {	
    static int N;
    static int[] streetlamp;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine()); // 굴다리 길이
        int M = Integer.parseInt(br.readLine()); // 가로등 개수
		
        streetlamp = new int[M];
		
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<M; i++) {
            streetlamp[i] = Integer.parseInt(st.nextToken());
        }
		
        int left = 1; // 굴다리 최소 크기
        int right = N;
        int ans = 0;
		
        while (left <= right) {
            int mid = (left + right) / 2;
			
            if (canLight(mid)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
		
        System.out.println(ans);
    }
	
    public static boolean canLight(int h) {
        int prev = 0;
		
        for (int i=0; i<streetlamp.length; i++) {
            if (streetlamp[i] - h <= prev) {
                prev = streetlamp[i] + h;
            } else {
                return false;
            }
        }
		
        // 마지막 가로등이 비추는 곳이 굴다리 길이보다 같거나 커야함
        return N - prev <= 0;
    }
}