[백준/Java] 17266번 : 어두운 굴다리

✏️ 문제 분석

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

 

길이가 N인 굴다리에 가로등 M개를 설치한다.

가로등 높이가 H이면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비출 수 있다.

최소한의 높이로 굴다리 전체를 밝히고자 할 때, 가로등의 최소 높이를 구하는 문제이다.

✏️ 구현 아이디어

브루트 포스는 시간 초과

우리가 구해야 하는 것은 가로등 높이의 최소값이다.

가로등 높이를 h라고 하면, h가 될 수 있는 값은 1~N이다.

 

브루트 포스로 푼다면

h가 1일 때, 2일 때, ..., N일 때 굴다리 전체를 밝힐 수 있는지 가로등 마다 확인해야 한다. 

가로등 개수는 M개 이므로 전체 시간 복잡도는 O(N*M)이다.

 

최악의 경우 100,000*100,000번 연산이 필요하다.

따라서 탐색 시간을 더 줄여야 한다.

 

h를 1~N까지 모두 탐색하는 로직이 시간 복잡도에 가장 많이 기여하는 부분이므로

h를 탐색할 때 시간복잡도가 O(logN)인 이분탐색을 사용해보자.

 

이분 탐색으로 풀기

h가 될 수 있는 값 중 최소값을 찾아보자.

 

h의 최소값은 1, 최대값은 N이므로 

left=1, right=N, mid=(left+right)/2

 

그리고 이분 탐색을 할 때 h가 mid일 때 굴다리를 모두 밝힐 수 있으면

더 작은 h값을 찾기 위해 right=mid-1

밝힐 수 없으면 더 큰 h값을 찾기 위해 left=mid+1

 

---

5
2
2 4

 

첫 번째 탐색 :

left=1, right=5, mid=(1+5)/2=3

높이 3인 가로등으로 굴다리 전체를 밝힐 수 있으므로 h의 범위를 mid 앞쪽으로 변경 

right=3-1=2

 

두 번째 탐색 :

left=1, right=2, mid=(1+2)/2=1

높이 1인 가로등으로 굴다리 전체를 밝힐 수 있으므로 h의 범위를 mid 앞쪽으로 변경

right=1-1=0

 

right<left이므로 탐색 종료

---

* 굴다리 전체를 밝힐 수 있는지 확인하는 로직 :

현재까지 밝힌 범위의 끝을 저장할 prev를 선언한다. (prev의 초기값은 0으로 세팅됨)

prev=0

 

각 가로등에 대해 light[i]-h가 prev를 초과하면 굴다리가 밝히지 못하는 영역이 존재하는 것이므로 false를 리턴

light[i]-h가 prev를 초과하지 않으면 다음 i에 대해 검사하기 위해 prev=light[i]+h로 갱신

모든 가로등을 확인했다면 N<=prev인지 확인하고

모든 조건을 통과했다면 true를 리턴 

 

✏️ 알고리즘

이분탐색 알고리즘 (이유는 앞서 설명함)

✏️ 시간 복잡도

이분탐색은 시간 복잡도가 O(logN)이다.

탐색할 굴다리의 길이가 최대 100,000이므로 시간 안에 연산 가능하다.

✏️ 코드 설계

1. 입력 받기
2. light[]에 가로등 위치 저장
3. 이진 탐색
   1. 이진 탐색 범위를 1~N으로 설정한다. 
   2. 현재 탐색 중인 높이를 mid로 두고 이진 탐색
   3. isPossible로 굴다리를 모두 밝힐 수 있는지 검사
      1. mid로 굴다리를 모두 밝힐 수 있으면 더 작은 범위로 조정
      2. mid로 굴다리를 모두 밝힐 수 없으면 더 큰 범위로 조정
   4. 모든 가로등 확인 후 굴다리 끝까지 확인 (N-prev)

✏️ 정답 코드

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

public class Main {
    static int N;
    static int[] light;


    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());

        light = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i=0; i<M; i++) {
            light[i] = Integer.parseInt(st.nextToken());
        }

        int left = 1; //굴다리 최소 크기
        int right = N;
        int ans = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (isPossible(mid)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(ans);
    }

    public static boolean isPossible(int h) {
        int prev = 0;

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

        //마지막 가로등 확인
        return N - prev <= 0;
    }
}