[백준][BOJ 17266] - 어두운 굴다리

문제

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

17266번: 어두운 굴다리

 

 

문제 접근

• 나이브한 풀이로는 완전 탐색을 사용하는 방법이 있다.
  • 가장 심플한 풀이 방식으로 가로등의 높이로 있을 수 있는 모든 범위($1 \leq h \leq N$)에 대하여 길의 모든 부분이 밝혀질 수 있는지를 체크하는 방법을 사용하는 것이다.
  • 하지만 해당 방식을 사용하면 적어도 $O(N^2)$의 시간이 걸리기 때문에 $h$가 10만까지 올라가는 특성 상 시간 초과가 나게 될 것이다.
• 다른 방식으로는 가로등의 최소 높이를 구하라는 것에 유의한 이분 탐색 방식이 있다.
  • 가로등의 높이 $h$는 최소 1에서 최대 10만까지이다. 여기서 절반씩 탐색하며 모든 범위를 비출 수 있는 가로등의 높이 범위를 좁혀 나가는 것이다.
  • 이러면 높이가 10만까지 가능하더라도 많아봐야 17번 정도의 탐색을 통해 특정시킬 수 있게 된다.
• 문제는 위 방식을 사용할 시 어떻게 모든 부분이 안전한지를 확인하냐는 것이다.
  • 가로등의 위치를 $x$라고 할 때 높이가 $h$라면 $x - h$ 부터 $x + h$까지는 무조건 안전하다는 것을 이용한다.
  • 가로등의 위치를 저장한 뒤 이전 가로등이 비추는 최대 한계점과 현재 가로등이 비추는 최소 한계점을 비교하여 최소 한계점이 더 크다면 비어 있는 공간이 존재한다는 것이므로 모든 공간을 비출 수 없다는 것이 된다.
  • 예를 들어 가로등의 위치가 각각 1, 4이고 높이가 1이라면 다음과 같이 확인할 수 있다.
    • 위치 1의 가로등은 최소 0에서부터 최대 2까지를 비출 수 있다.
    • 위치 4의 가로등은 최소 3에서부터 최대 5까지를 비출 수 있다.
    • 이때 위치 1의 최대 한계점인 2보다 위치 4의 최소 한계점인 3이 더 크므로 모든 부분을 비출 수 없다는 것을 확인할 수 있다.

 

 

정답 코드

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int M = Integer.parseInt(br.readLine());

    int[] lampLocation = new int[M];
    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i = 0; i < M; i++){
      int location = Integer.parseInt(st.nextToken());
      lampLocation[i] = location;
    }

    int start = 1;
    int end = N;
    int ans = 0;

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

      int temp = 0;
      for (int location: lampLocation){
        if (location - mid > temp){
          start = mid + 1;
          break;
        }

        temp = location + mid;
      }

      if (temp < N){
        start = mid + 1;
        continue;
      }

      ans = mid;
      end = mid - 1;
    }

    System.out.println(ans);
  }
}