[BOJ 17266] 어두운 굴다리 (Java, 매개변수 탐색)

 

 

 

---

문제 링크

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

17266번: 어두운 굴다리

---

풀이

- 이진탐색(매개변수 탐색) 문제  

- 시간복잡도 O(NlogN)

- 굴다리 길이 N (1 ≤ N ≤ 100,000) 일 때 0번 위치에 가로등 한 개 세울 경우 H는 100,000(최대)이 되야 모두 비추는게 가능하므로 Integer로 연산가능

 

뒤집은 문제

가로등 높이 H일 때 굴다리 길이 N을 모두 비추는게 가능한가? 가능한 경우 가로등 높이 H는 최소 높이인가?

 

예제 입력 1
5
2
2 4

예제 출력 1
2

 

예제 입력에서 가로등 높이 H = 3인 경우에도 굴다리 길이 5만큼 모두 비추는게 가능함.

하지만 H = 2 인 경우에도 굴다리 길이만큼 모두 비추는게 가능하기 때문에 정답은 2가 됨 

 

매개변수 탐색에서 주어진 조건을 만족하는 경우 아래와 같이 범위 조정 후 재탐색
- 최소값을 찾는 경우 R을 감소
- 최대값을 찾는 경우 L을 증가

 

---

제출 코드

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

public class Main {

    static int N, M;

    static int[] PolePoint;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

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

    static boolean isValid(int height) {
        int last = 0;
        for(int p : PolePoint) {
            if(p - last <= height) {
                last = p + height;
            } else {
                return false;
            }
        }

        return last >= N; // 마지막 위치보다 전등 빛 범위가 클 때
    }

    static void pro() {
        int L = 1, R = 100000, ans = 0;
        while(L <= R) {
            int mid = (L + R) / 2;
            if(isValid(mid)) { //최소 높이이므로 조건 성립시 R을 줄임
                R = mid - 1;
                ans = mid;
            } else {
                L = mid + 1;
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}