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

🔺 문제

17266번: 어두운 굴다리

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] A;
    static int N, M;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());    // 굴다리 길이
        M = Integer.parseInt(br.readLine());    // 가로등 개수
        A = new int[M];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < M ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
 
        // 🔔 이분 탐색        
        int l = 1;
        int r = N;
 
        int result = 0;    // 최소 높이
        
        while(l <= r) {
            int mid = (l + r) / 2;
            
            if(possible(mid)) { // 모든 지점을 비출 수 있는 경우
                result = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        
        System.out.println(result);
    }
    
    private static boolean possible(int target) {
        int prev = 0; // 이전 가로등이 비춘 마지막 지점
        
        for(int i = 0 ; i < A.length ; i++) {
            if(A[i] - target <= prev) { // 이전 가로등이 마지막으로 비춘 지점을 도달한다면
                prev = A[i] + target; // 가로등이 마지막으로 비춘 지점 갱신
            }
            else {
                return false;
            }
        }
        
        return N - prev <= 0; // N까지 거리가 0 이하인지 확인
    }
}
 

✅ 해결 아이디어
✔ 이분 탐색

 

💥 유의사항

• 완전탐색으로 풀면 아찔..

 

---

🔺 다른 풀이들

- 다들 비슷하심

 

---

💬 느낀 점

만만하게 봤다가 제대로 못 품......

이분 탐색 언제쯤 잘 할래 정말...🤦‍♀️

 

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

[백준_17266번] 어두운 굴다리

 

[자바로 푸는 백준] 17266번 어두운 굴다리