어두운 굴다리 (BOJ 17266)

어두운 굴다리 (BOJ 17266)

📖 문제 설명

길이 N의 굴다리에 M개의 가로등이 설치되어 있다.

각 가로등은 높이 H만큼 좌우를 비출 수 있다.

굴다리 전체를 밝히기 위한 최소 가로등 높이 H를 구하는 문제이다.

✅ 조건 정리

• N : 굴다리 길이

• M : 가로등 개수

• 가로등 위치는 오름차순으로 주어짐

• 모든 구간이 어둡지 않도록 해야 함

• 구해야 하는 것 → 최소 높이 H

💡 풀이 방법

굴다리를 밝히기 위해 고려해야 할 구간은 3가지이다.

1️⃣ 왼쪽 끝 구간

굴다리 시작점(0)부터 첫 번째 가로등까지의 거리

x[0]

이 값만큼은 비춰야 한다.

2️⃣ 가로등 사이 구간 (핵심)

두 가로등 사이의 거리:

x[i] - x[i-1]

이 구간은 양쪽 가로등이 절반씩 비추므로

필요한 높이는

ceil((거리) / 2)

정수 올림 처리를 위해:

(x[i]-x[i-1]+1)/2

을 사용한다.

3️⃣ 오른쪽 끝 구간

마지막 가로등부터 굴다리 끝까지의 거리

N - x[M-1]

🎯 최종 아이디어

위 세 구간 중

가장 큰 값이 최소 가로등 높이 H가 된다.

💻 코드

package boj;

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

public class Boj17266 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[] x = new int[M];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            x[i] = Integer.parseInt(st.nextToken());
        }

        // 각각의 가로등 위치사이 간격의 최대값을 구하기
        int maxDist = x[0];

        for (int i = 1; i < M; i++) {
            int dist = (x[i] - x[i-1] + 1) / 2;
            if (maxDist < (dist)) {
                maxDist = dist;
            }
        }

        // 최대값 구한 후 마지막을 비출 수 있는지 구하기
        maxDist = Math.max(maxDist, N - x[M-1]);

        System.out.println(maxDist);
    }
}

⏱ 시간 복잡도

• 시간복잡도: O(M)

• 공간복잡도: O(M)

🔎 핵심 포인트 정리

• 가로등 사이 간격은 그대로 사용하면 안 된다.

• 반드시 2로 나누고 올림 처리해야 한다.

• 왼쪽 끝, 오른쪽 끝도 따로 비교해야 한다.

• 최댓값을 구하는 문제로 변환하면 쉽게 해결된다.