백준 17266 - 어두운 굴다리 (자바 - 이분탐색)

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

17266번: 어두운 굴다리

 

* 문제 요약

인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다.

따라서 굴다리로 가면 최단거리로 집까지 갈 수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다.

안타깝게 여긴 인식이는 굴다리 모든 길 0 ~ N 을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다.

인천광역시에서 가로등을 설치할 갯수 M과 각 가로등의 위치 x 들의 결정을 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을 수록 가격이 비싸지기 때문에 최소한의 높이로 모든 길 0 ~ N 을 밝히고자 한다. 최소한의 예산이 들 높이를 구하자.

단, 가로등은 모두 높이가 같아야 하고, 정수이다.

 

다음 그림을 보자.

다음 그림은 예제 1에 대한 설명이다.

가로등의 높이가 1일 경우 0~1 사이의 길이 어둡기 때문에 상빈이는 지나가지 못한다.

아래 그림처럼 높이가 2일 경우 0~5 의 모든 길이 밝기 때문에 상빈이는 지나갈 수 있다.

 

* 입력

첫 번째 줄에 굴다리의 길이 N이 주어진다. (1 <= N <= 100,000)

두 번째 줄에 가로등의 갯수 M이 주어진다. (1 <= M <= N)

다음 줄에 M개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 <= x <= N)

가로등의 위치 x 는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

 

* 출력

굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이를 출력한다.

 

* 예시

 

* 해결 과정

가로등의 각 위치에 대한 정보가 입력으로 들어올 때 해당 정보들을 배열에 저장해주었다.

이때 각 위치에 대한 정보는 기본적으로 오름차순으로 들어오므로 따로 정렬을 수행해줄 필요가 없다.

다음은 아래와 같은 방식으로 이분탐색을 수행한다.

1. start, end 두 변수를 선언하고 각각 0, 굴다리의 길이 값으로 초기화 해준다.

2. start <= end 조건을 만족하는 동안 다음과 같이 반복문을 수행한다.

  - mid 변수를 선언하고 (start + end) / 2 값을 저장해준다.

  - mid 값을 파라미터로 하는 lightCheck(int mid) 메소드를 수행해준다.

  * lightCheck(int mid) 메소드 로직은 아래와 같다.

    - mid 값을 가로등의 현재 높이로 취급한다.

    - prev 변수를 선언한다. 이 변수는 이전 위치의 램프에 불이 들어왔을 때, 현재 높이에서 밝힐 수 있는 영역 중 오른쪽 끝 부분을 의미한다.

    - 가로등의 위치가 입력된 배열을 처음부터 끝까지 탐색하되 다음과 같은 로직을 수행한다.

    - 만약 lampArray[i] - mid <= prev 인 경우. 다시 말해 현 위치의 가로등이 밝힐 수 있는 영역 중 왼쪽 끝에 해당하는 부분이 이전 가로등이 밝힌 영역 중 오른쪽 끝 보다 앞서 있거나 같은 위치인 경우. 즉, 이전 가로등과 현재 가로등 사이의 공간을 빈틈없이 밝힐 수 있는 경우 prev 변수에 현재 가로등이 밝힐 수 있는 영역 중 오른쪽 끝 부분 위치 (lampArray[i] + mid) 를 저장하고 다음으로 넘어간다.

    - 만약 위의 조건을 만족하지 못한다면. 다시 말해 이전 가로등과 현재 가로등 사이에 밝힐 수 없는 빈틈이 존재하는 경우 즉시 반복문을 종료한다.

    - 반복문이 끝난 이후 만약 prev 변수의 값. 즉, 반복문이 끝나기 직전에 밝힌 가로등이 밝힐 수 있는 영역 중 오른쪽 끝 부분이 굴다리의 길이보다 작다면 (bridgeLength - prev > 0) 현재 mid 값을 높이로 해서 가로등을 설치할 경우 모든 굴다리의 영역을 밝힐 수 없다는 뜻이므로 false 를 리턴해준다.

    - 반대로 bridgeLength - prev 값이 음수라면, 반복문이 끝나기 직전 밝힌 가로등이 밝힐 수 있는 영역 중 오른쪽 끝 부분이 굴다리의 길이보다 길다는 뜻인데, 이는 현재 mid 값을 가로등의 높이로 하였을 때 굴다리 전체를 빈틈없이 밝혀줄 수 있다는 뜻이므로 true 를 리턴한다.

 

  - 만약 lightCheck(int mid) 메소드에서 true 를 리턴받은 경우 결과값 변수 result 에 현재 mid 값을 저장해주고 난 다음, 더 작은 값으로도 되는 경우가 있는지 확인해보기 위해 end 변수에 mid - 1 을 저장하여 mid 값으로 지정될 수 있는 숫자의 크기를 줄여준다.

  - 만약 lightCheck(int mid) 메소드에서 false 를 리턴받은 경우 따로 결과값을 저장해주지 않고 start 변수에 mid + 1 을 저장하여 mid 값으로 지정될 수 있는 숫자의 크기를 늘려준다.

 

3. 위와 같은 과정을 거쳐 얻은 result 값을 최종적으로 출력해줌으로서 문제를 해결하였다.

 

* 코드

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

public class Main {

    static int[] lampArray;
    static int bridgeLength;

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bridgeLength = Integer.parseInt(br.readLine());

        int count = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        lampArray = new int[count]; 
        for (int i = 0; i < lampArray.length; i++) {
            lampArray[i] = Integer.parseInt(input[i]);
        }

        int start = 0;
        int end = bridgeLength;
        int result = 0;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (lightCheck(mid)) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private boolean lightCheck(int mid) {
        int prev = 0;

        for (int i = 0; i < lampArray.length; i++) {
            if (lampArray[i] - mid <= prev) {
                prev = lampArray[i] + mid;
            } else {
                return false;
            }
        }

        if (bridgeLength - prev > 0) {
            return false;
        } else {
            return true;
        }
    }
}

 

굴다리의 시작지점 0, 굴다리의 전체 길이 bridgeLength 를 첫 번째 기준으로 하고, 그 사이에 있는 mid 값을 가로등의 높이로 하여 굴다리 전체를 밝힐 수 있는 경우와 그러지 못하는 경우로 나누면서 범위를 좁혀가며 문제를 해결하였으므로 이분탐색 문제에 해당된다.