문제 이해

지정한 위치에 가로등을 설치할 것이다.
이 때 H라는 값이 주어질 것인데, 존재하는 모든 가로등은 왼쪽으로 H만큼, 오른쪽으로 H만큼 불빛을 비출 수 있다.

즉, 가로등의 위치가 x일 때 x-H<= T <= x+H인 T에는 불빛이 비추는 것이다.

굴다리의 길이가 N일 때, 0 ~ N까지 불빛이 모두 비추게 하는 H값 중 최소값을 구하는 것이 문제이다.

문제 풀이

내가 임의로 지정할 수 있는 값은 오직 하나, H이다.
즉 H를 적절히 조절하여 문제를 풀어야 한다고 생각할 수 있다.

배열에 x y값이 인접한 위치에 존재한다고 생각하자

먼저, x-H이상 x+H이하의 구간에 빛이 비출 것이다.
이후 y에서의 상황을 보자. 이 곳에서는 y-H이상 y+H 이하의 구간에 빛이 비출 것이다.

1. y-H > x+ H : x+H ~ y-H 사이의 구간에는 빛이 비추지 않는다. 즉, 문제의 조건에 어긋난다.

2. y-H <= x+H : 겹치는 구간이 존재하지만 모든 구간에 빛이 비춘다.

즉, 모든 인접한 좌표에 대해 2번 조건을 충족시킨다면 문제의 조건을 충족시키는 H라고 할 수 있을 것이다.
이 때 중요한 점이 있다.

먼저 x < y일 것이므로 x+H < y+H일 것이다. 따라서, x와 y좌표에 존재하는 가로등이 빛을 비추는 범위는 x-H 이상 y+H 이하의 구간일 것이다.
y이후 인접한 좌표가 z일 때, z-H는 y+H 이하이면 된다.

즉, 2번 조건을 충족시킨다면 이 때의 y+H값을 임시로 저장하자.(이 값을 last라고 하자)
이후 last와 z-H를 비교한다.
만약 last >= z-H라면 y+H >= z-H라는 의미이고, x y z에 대해 모든 구간에 빛을 비추는 것이다.
반대로 last < z-H라면 y+H< X < z-H인 정수 X가 존재한다는 의미이므로, 빛이 비추지 않는 구간이 존재한다는 것이고, 이는 문제의 조건에 맞지 않으므로 무시하면 되는 Case이다.

마지막으로, 저장된 last는 무조건 N이상이여야 한다. 만약 N보다 작다면, 빛이 비추는 마지막 구간이 N보다 작다는 의미이므로 last ~ N 사이 구간에는 빛이 비추지 않을 것이기 때문이다.

이 때 상황은 2개 존재한다.

1. 0 ~ N 모든 구간에 빛이 비춤 : 정답이 될 수 있는 후보
   우리는 H 최솟값을 구하고 싶기 때문에 right값 변경

2. 모든 구간에 빛이 비추지 않음 : 정답이 될 수 없음
   빛을 비추는 범위를 늘려야 하므로 H값을 증가시켜야 하기 때문에 left값 변경

위 조건을 활용하여 이분탐색을 통해 문제를 해결하였다.

코드

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

public class Main {
	static int N, K;
	static Integer[] arr;
	
	static boolean search(int value) {
        // 0 ~ N 모든 곳에 빛이 비추면 True, 아닐 경우 False 반환
        
        int last = 0;  // 빛으로 밝혀진 위치 중 가장 오른쪽 좌표.
        for (int i = 0; i < K; i++) {
            if (arr[i] - last <= value) {
                // last >= arr[i] - value
                // 인접한 구간에 대하여 빛이 끊기지 않는다는 의미이다.
                // 문제 풀이에서 설명했던 것처럼 last값을 갱신시켜준다.
                last = arr[i] + value;
            } else {
                // last ~ arr[i]-value 구간에 빛이 비추지 않는다. 
                // 따라서 False를 반환한다.
                return false;
            }
        }
        return last >= N;
        // 마지막에 빛을 비추는 범위는 N 이상이여야만 
        // 모든 좌표에 빛이 비추는 것이다.
	}
	
	
	static void min_height() {
		int left = 0;
		int right = 100000;
        // 좌표의 위치는 0부터 최대 100000이므로, 
        // 이 값을 활용하여 left와 right를 지정하였다.
		int mid;
		int ans = N;
		
		while(left <= right) {
			mid = (left+right)/2;
			if(search(mid)) {
                // 모든 구간에 빛이 비추는 상황
				ans = mid;
				right = mid - 1;
			}
			else {
                // 특정 구간에 빛이 비추지 않는 상황.
				left = mid + 1;
			}
		}
		
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		K = sc.nextInt();
		arr = new Integer[K];
		
		for(int i =0;i<K;i++) {
			arr[i] = sc.nextInt();
		}
		
		min_height();
	}
	
	static class FastReader //빠른 입력을 위한 클래스
}

결과

• 4,5 번째 틀렸습니다 : 내가 이 문제를 풀기 전에는 항상 현재 ⇒ 미래를 상상하는 식으로 문제를 해결하였다. 나중에 DP문제를 해결할 때 이 문제가 더욱 도드러져 수정을 하는데 매우 많은 애를 먹었다.

  알고리즘 문제를 해결할 때는 주로 현재 상황에서 과거 상황을 읽어들이는 것이 더욱 코드 짜기가 쉽다. 현재에서 미래를 상상하다보니 내 생각이 복잡해지고, 코딩테스트를 연습하기 위해 종이를 활용하지 않았기 때문에 복잡한 생각을 정리할 수 없어 생긴 문제였다. 항상 현재에서 과거의 정보를 읽어들이는 방식을 활용하자

• 3번째 에러 : 실수로 Array를 Search하는 범위를 잘못 지정했다.

• 1번째 틀렸습니다 : 4번째 틀렸습니다 틀린 이유 확인하다 실수로 제출누름

현재 ⇒ 미래를 파악한다는 것이 무슨 의미인가

• x에 1을 더하거나 뺄 수 있다고 가정하자. 나는 항상 x라는 현재 상황에서 x+1인 상황과 x-1인 상황을 모두 고려하는 방식을 활용하였다

• 하지만 문제 해결을 하다보니, x+1인 상황과 x-1인 상황을 "현재"로 두고 과거의 x인 상황을 읽는 것이 효율적인 경우가 많다는 것을 알 수 있었다.

• 이 문제는 내가 이전까지 DP에서 매우 큰 어려움을 겪는 이유이기도 했다. 이 부분을 자세히 알고 싶다면 "2096 내려가기" 문제 풀이를 읽어보자