[BJ]17266 어두운 굴다리

BJ S5 17266 어두운 굴다리

 

 

문제링크

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

17266번: 어두운 굴다리

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ S5 17266 어두운굴다리 - YouTube

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * 
 * @author 은서파
 * @since 2021/12/07
 * @see https://www.acmicpc.net/problem/17266
 * @performance 반복문: 25328 236, 이분탐색: 25428 252
 * @category #반복문, #이분탐색
 */

public class BJ_S5_17266_어두운굴다리 {
    private static StringBuilder output = new StringBuilder();
    static int N, M;
    static int[] pos;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        N = Integer.parseInt(input.readLine());
        M = Integer.parseInt(input.readLine());
        pos = new int[N];
        StringTokenizer tokens = new StringTokenizer(input.readLine());
        for (int m = 0; m < M; m++) {
            pos[m] = Integer.parseInt(tokens.nextToken());
        }
        //loop();
        binarySearch();
    }

    private static void binarySearch() {
        // 1. 이분 탐색 전제 조건: 요소들이 정렬된 상태여야 한다.!
        // 2. 기준 값들은?
        int l = 1, r = N, m = 0;
        int sol = Integer.MAX_VALUE;
        boolean flag = false;
        while (l <= r) {
            m = (l + r) / 2;
            flag = true;
            // 맨 왼쪽 가로등
            if (pos[0] - m > 0) {
                flag = false;
            } else if (pos[M - 1] + m < N) {
                flag = false;
            } else {
                for (int i = 1; i < M - 1; i++) {
                    if (pos[i] + m < pos[i + 1] - m) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                sol = Math.min(sol, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        System.out.println(sol);
    }

    private static void loop() {
        boolean flag = false;
        for (int h = 1; h <= N; h++) {
            flag = true;
            // 맨 왼쪽 가로등
            if (pos[0] - h > 0) {
                flag = false;
            } else if (pos[M - 1] + h < N) {
                flag = false;
            } else {
                for (int i = 1; i < M - 1; i++) {
                    if (pos[i] + h < pos[i + 1] - h) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                System.out.println(h);
                break;
            }
        }
    }

    // REMOVE_START
    private static String src = "5\n" +
                                "2\n" +
                                "2 4";
    // REMOVE_END
}