[백준 17266] 어두운 굴다리 (JAVA)

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

17266번: 어두운 굴다리

 

 

이분탐색으로 해결해야하는 문제였다..

start =1 , end=n으로 설정하여 mid값을 돌리면서 

높이값을 mid로 했을때 모든 거리를 비추는지 확인한다!

모두 비추면 end값을 mid-1로 해준다.

그렇게 해서 최소의 높이 값을 찾는다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int[] light;
	static int n,m;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 n = Integer.parseInt(br.readLine());
		 m = Integer.parseInt(br.readLine());
		light=new int[m];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			light[i]=Integer.parseInt(st.nextToken());
		}
		int start =1;
		int end=n;
		int result=0;
		
		//이분탐색
		while(start<=end) {
			int mid = (start+end)/2;
			
			if(check(mid)) {
				result=mid;
				end=mid-1;
			}
			else start=mid+1;
		}
		
		System.out.println(result);
	}

	static boolean check(int t) {
		int prev = 0;
		for(int i=0;i<m;i++) {
			if(light[i]-t<=prev) prev=light[i]+t;
			else return false;
		}
		return n-prev<=0; //n까지 거리가 0이하인지 체크!
	}
}