[BOJ] 17266 어두운 굴다리 - JAVA

1. 문제

17266번: 어두운 굴다리

인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈 수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다. 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정을 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을수록 가격이 비싸지기 때문에 최소한의 높이로 굴다리 모든 길 0~N을 밝히고자 한다. 최소한의 예산이 들 높이를 구하자. 단 가로등은 모두 높이가 같아야 하고, 정수이다.
다음 그림을 보자.

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

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

---

2. 풀이

1.  이분탐색을 사용했다. left = 0, right = N+1로 둔다. 최악의 경우 하나의 가로등이 굴다리 길이만큼 비춰야 할 수 있기 때문이다.
2.  이전값을 prev에 저장하고, 현재 탐색하려는 가로등이 빛을 비췄을 때 prev에 도달하지 못하면 그 만큼을 count에 추가한다.
3.  현재 탐색하는 가로등이 오른쪽을 m만큼 비추기 때문에 prev는 light+m값으로 교체한다.
4.  탐색이 끝나면 마지막 가로등의 오른쪽이 N(굴다리 끝) 에 도달하는지 확인하고, 도달하지 못하면 count에 추가한다.
5.  2,4에서 빛이 비추지 않는 만큼을 count에 더했지만, 사실 이 문제는 count가 0인지 0이 아닌지가 중요한 문제다. count가 0보다 크다면 가로등의 높이를 높여야하므로 l=m+1한다. count==0이라면 r=m-1해서 최솟값을 찾는다.
6.  l을 출력한다.

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

public class BOJ_17266_어두운굴다리 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());
      int[] lights = new int[M];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<M;i++) lights[i] = Integer.parseInt(st.nextToken());

      int l = 0, r = N+1, m, prev, count;
      while(l<=r){
         m = (l+r)/2;
         prev = 0;
         count = 0;
         for(int light:lights){
            if(light-m > prev) count += light-m-prev;
            prev = light+m;
         }
         if(lights[M-1]+m < N) count += N-lights[M-1]-m;

         if(count > 0){
            l = m+1;
         }else{
            r = m-1;
         }
      }

      System.out.println(l);
   }
}

---

3. 결과

l의 max값을 실수로 N+1이 아닌 M+1로 해서 틀렸다 ^^..
int count->boolean flag로 변경해서 해봤는데 별로 유의미한 차이는 없었다.