문제

어두운 굴다리

풀이

한번 트라이 했는데, 틀렸다 범위가 틀렸었다. 마지막에 모두 다 커버 된 경우의 주석을 보면
같은 경우까지 covered 했다고 봐야 하기 때문에...

		int left = 0;
        int right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            int current = 0;
            for (int c : x) {
                int start = c - mid;
                int end = c + mid;
                if (current < start) { // cover 불가
                    break;
                } else {
                    current = end;
                }
            }
            if (n <= current) { // 모두 다 covered
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);

검색해서 보다가 풀이가 나랑 조금 달라서 별로 참고가 안되서 ㅠㅡㅠ 괜히 헤맸다 생각보다 정말 간단하게 해결,, 이분탐색 너무오래간만에 풀었나.

전체 코드

전체 코드