백준 17266번: 어두운 굴다리 (C++ 풀이)

백준 17266 어두운 굴다리 C++

문제

문제 설명

인하대학교 후문 뒤에는 어두운 굴다리가 있습니다. 겁이 많은 상빈이는 길에 조금이라도 어두운 부분이 있으면 지나가지 않습니다. 따라서 굴다리를 지나가기 위해서는 0 ~ N까지 모든 구간이 밝아야 합니다.

인천광역시는 굴다리를 밝히기 위해 M개의 가로등을 설치합니다. 각 가로등은 같은 높이 H를 가지며, 높이 H라면 왼쪽과 오른쪽으로 H만큼 구간을 밝힙니다.

목표: 굴다리 전체를 덮을 수 있는 최소한의 H를 구하세요.

---

입력

1. 첫 줄에 굴다리의 길이 N (1 ≤ N ≤ 100,000)
2. 둘째 줄에 가로등 개수 M (1 ≤ M ≤ N)
3. 셋째 줄에 M개의 가로등 위치 (0 ≤ x ≤ N, 오름차순)

---

출력

• 모든 구간 [0, N]을 덮기 위한 최소 H를 출력

---

테스트케이스

예제 1

입력
5
2
2 4
출력
2

예제 2

입력
3
1
0
출력
3

---

아이디어

굴다리를 전부 덮기 위해서는 크게 세 가지 조건이 필요합니다.

1. 앞 구간: 시작점 0부터 첫 번째 가로등까지
   • 조건: H ≥ arr[0]
2. 중간 구간: 인접한 가로등 사이
   • 두 가로등 위치가 a, b라면 거리는 d = b - a
   • 조건: H ≥ ceil(d/2)
   • 코드에서는 (d+1)/2로 계산
3. 끝 구간: 마지막 가로등부터 끝점 N까지
   • 조건: H ≥ (N - arr[M-1])

이 세 조건을 모두 만족해야 굴다리 전체가 덮입니다. → 따라서 정답은 세 조건을 만족하는 최소 H, 즉 이분 탐색으로 찾을 수 있습니다.

---

문제 풀이

우리가 풀어야 하는 문제는 “굴다리의 길이가 N이고, 특정 위치에 M개의 가로등이 설치되어 있을 때, 모든 길(0~N)을 밝히기 위한 최소 가로등 높이 H는 얼마인가?”입니다.

가로등의 높이가 H라면, 각 가로등은 자기 위치에서 왼쪽으로 H, 오른쪽으로 H 범위를 밝힙니다. 즉, 위치가 x인 가로등은 [x-H, x+H]를 덮습니다.

이때 중요한 점은 가로등들이 모두 같은 높이 H를 가진다는 점입니다. 따라서 우리는 “하나의 값 H”를 정했을 때 전체 [0~N]이 어두운 부분 없이 덮일 수 있는가를 따져야 합니다.

여기서 자연스럽게 세 가지 상황이 발생합니다.

1. 맨 앞 구간: 시작점 0부터 첫 번째 가로등 사이
2. 중간 구간: 가로등과 가로등 사이
3. 맨 끝 구간: 마지막 가로등부터 끝점 N까지

---

1. 맨 앞 구간: 0 ~ 첫 번째 가로등

왜 이 구간이 중요한가?

굴다리는 0부터 시작합니다. 첫 번째 가로등의 위치를 arr[0]이라고 합시다. 가로등은 자기 위치에서 왼쪽으로 H까지 비추므로, 만약 H < arr[0]이면 0번 위치는 절대 덮이지 않습니다. 따라서 조건 1: H ≥ arr[0]가 필요합니다.

예시: N=5, arr={2,4}

H=0일 때

• 가로등 2는 자기 자리만 비춥니다.

인덱스	0	1	2	3	4	5
상태	X	X	2	X	X	X

• 0, 1이 어둡습니다.
• 따라서 시작점 0이 커버되지 않아 실패.

H=1일 때

• 가로등 2는 [1~3]을 비춥니다.

인덱스	0	1	2	3	4	5
상태	X	O	2	O	X	X

• 0번 위치는 여전히 어둡습니다.
• 시작점 불통과.

H=2일 때

• 가로등 2는 [0~4]를 비춥니다.

인덱스	0	1	2	3	4	5
상태	O	O	2	O	O	X

• 0번 위치까지 덮입니다.
• 조건 충족.

→ 이 과정을 통해, “맨 앞을 덮으려면 \(H \ge arr[0]\)”이라는 조건이 도출됩니다.

---

2. 중간 구간: 가로등 사이

왜 이 구간이 중요한가?

가로등이 여러 개라면, 인접한 두 가로등 사이에 빈틈이 생길 수 있습니다. 예를 들어 위치가 a, b인 두 가로등이 있다면, 그 사이 거리 \(d = b - a\)가 있습니다. 두 가로등이 각각 H만큼 비추므로, 이 사이를 전부 덮으려면 다음이 필요합니다:

\[2H \ge d \rightarrow H \ge \text{ceil}(d/2)\]

즉, 조건 2: \(H \ge \text{ceil}((arr[i+1] - arr[i]) / 2)\)가 필요합니다.

예시: N=5, arr={2,4}

H=0일 때

• 가로등 2 → [2]
• 가로등 4 → [4]

인덱스	0	1	2	3	4	5
상태	X	X	2	X	4	X

• 3번이 어둡습니다.
• 두 불빛 사이에 빈틈이 생김. 실패.

H=1일 때

• 가로등 2 → [1~3]
• 가로등 4 → [3~5]

인덱스	0	1	2	3	4	5
상태	X	O	2	O	4	O

• 3번에서 두 불빛이 만남.
• 빈틈 없음. 성공.

H=2일 때

• 가로등 2 → [0~4]
• 가로등 4 → [2~6]

인덱스	0	1	2	3	4	5
상태	O	O	2	O	4	O

• 중간 구간은 완전히 덮임.
• 성공.

→ 이 과정을 통해, “가로등 사이 간격 d를 메우려면 \(H \ge \text{ceil}(d/2)\)”라는 조건이 필요함을 알 수 있습니다.

---

3. 끝 구간: 마지막 가로등 ~ N

왜 이 구간이 중요한가?

마지막 가로등 위치가 arr[M-1]이라고 합시다. 굴다리 끝은 N입니다. 따라서 마지막 가로등이 N까지 닿아야 합니다. 즉, 조건 3: \(H \ge (N - arr[M-1])\)입니다.

예시: N=5, arr={2,4}

H=0일 때

• 마지막 가로등(4) → [4]만 비춤.

인덱스	0	1	2	3	4	5
상태	X	X	X	X	4	X

• 5번 위치가 어둡습니다.
• 실패.

H=1일 때

• 마지막 가로등(4) → [3~5]

인덱스	0	1	2	3	4	5
상태	X	X	X	O	4	O

• 5번 위치가 밝습니다.
• 조건 충족.

H=2일 때

• 마지막 가로등(4) → [2~6]

인덱스	0	1	2	3	4	5
상태	X	X	O	O	4	O

• 끝까지 충분히 덮임.
• 조건 충족.

→ 이 과정을 통해, “끝까지 덮으려면 \(H \ge (N - arr[M-1])\)” 조건이 필요함을 알 수 있습니다.

---

최종 종합

지금까지 세 구간을 따로따로 살펴본 결과:

1. 앞 구간: \(H \ge arr[0]\)
2. 중간 구간: \(H \ge \text{ceil}((arr[i+1]-arr[i])/2)\)
3. 끝 구간: \(H \ge (N - arr[M-1])\)

따라서 전체를 덮기 위해서는

\[H \ge \max( arr[0], \max_{\text{all gaps}} (\text{ceil}(d/2)), N - arr[M-1] )\]

라는 하나의 식으로 정리됩니다. 즉, 최소 높이 H는 **세 구간 조건 중 가장 큰 값**입니다.

---

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

bool Check(int *arr, int M, int N, int H)
{
    // 앞 구간: 0이 덮이는지 확인
    if (arr[0] > H)
        return false;

    // 끝 구간: N이 덮이는지 확인
    if (N - arr[M-1] > H)
        return false;

    // 중간 구간: 가로등 사이 빈틈 확인
    for (int i = 1; i < M; i++)
    {
        if ((arr[i] - arr[i-1] + 1) / 2 > H)
            return false;
    }

    return true;
}

int main(void)
{
    int N, M, ans = 0;
    int arr[1000000];
    
    cin >> N >> M;
    for (int i = 0; i < M; i++)
        cin >> arr[i];

    int left = 0;
    int right = N;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (Check(arr, M, N, mid))
        {
            ans = mid;
            right = mid - 1; // 더 작은 높이가 가능한지 왼쪽 탐색
        }
        else
        {
            left = mid + 1; // 불가능하므로 오른쪽 탐색
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

---

정리

• 이 문제는 전체 구간을 세 부분으로 나누어 조건을 점검하는 것이 핵심입니다.
• 앞 구간: 시작 0을 덮기 위해 \(H \ge arr[0]\)
• 중간 구간: 인접 가로등 사이 빈틈 없게 \(H \ge \text{ceil}(\text{gap}/2)\)
• 끝 구간: 마지막 가로등에서 끝까지 덮기 위해 \(H \ge N - arr[M-1]\)

이 조건을 만족하는 H 중 최소값을 **이분 탐색**으로 찾아 출력합니다. 최종적으로 시간복잡도는 \(O(M \log N)\)으로, N이 최대 100,000이어도 충분히 빠르게 동작합니다.