자바(백준) 17266 어두운 굴다리

오답 노트 & 새로 알게 된 점

이 문제를 풀면서 possible에서 구현 생각하는게 좀 힘들었다.

처음에는 가로등의 count 개수에 따라 문제를 풀었는데, 틀렸다.

 

다시 생각해보니 가로등의 개수는 고정되있다. 

possible은 높이에 따라 비출 수 있는지 없는지 true, false를 반환해야한다.

그래서 높이가 N보다 크거나 같으면 당연히 모두 비출 수 있고,

일정 높이 이상이면 무조건 true이다. 이제 true에서 가장 왼쪽 값(최소 높이)를 구하면 된다.

 

possible에서 이제 어떻게 N까지 비출 수 있는지 확인해야한다.

last라는 마지막에 비추는 값을 의미하는 변수를 만든다.

가로등이 있는 위치에서 last를 뺀 값이 높이보다 작거나 같으면 앞이 다 비춰진다.

그래서 last에 가로등이 있는 위치에서 높이만큼 더해준 값을 넣는다.

마지막 last의 값이 N보다 크거나 같게 되면 모두 다 비출 수 있게 된다.

 

---

코드

package Binary_Search;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N; //굴다리 길이
    static int M; //가로등의 개수
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        M = atoi(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        A = new int[M];
 
        for (int i = 0; i < M; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        paraSearch();
    }
 
    //높이가 target으로 들어옴
    static boolean possible(int target) {
        int last = 0; //밝혀진 마지막 위치
 
        for (int i = 0; i < M; i++) {
            if(A[i] - last <= target){
                last = A[i] + target;
            }
            else return false;
        }
        return last >= N;
    }
 
    static void paraSearch() {
        int s = 0, e = 100000, rel = 0;
 
        while (s <= e) {
            int mid = (s + e) / 2;
 
            if (possible(mid)) {
                rel = mid;
                e = mid - 1;
            }
            else s = mid + 1;
        }
 
        System.out.println(rel);
    }
}