[백준] 어두운 굴다리 (17266번)

난이도 : Silver 4
Link : https://www.acmicpc.net/problem/17266
Tag : 구현, 이분탐색
풀이일자 : 2024년 9월 21일

📌 문제 탐색하기

N : 굴다리의 길이
M : 가로등의 개수
locate : 가로등의 위치
height : 가로등 높이

이 문제는 주어진 굴다리 길이에서 가로등으로 비출 수 있는 최소 높이로 모든 곳을 비추게 하는 것이 목표이다.

가능한 시간복잡도

가로등이 없는곳에서 - 첫번째 가로등
가로등과 가로등
마지막 가로등에서 - 가로등이 없는 길

이렇게 3가지로 나눠 3가지 거리중 가장 큰 값을 비출 수 있는 최소 높이를 구하게 되면 문제를 해결할 수 있다.
따라서 가로등의 개수의 따라 시간복잡도는 달라지므로 O(m)이 된다.

📌 문제 접근 방법

가로등이 없는곳 - 첫번째 가로등
가로등과 가로등의 거리
마지막 가로등 - 가로등이 없는곳

3가지 거리를 구하고 3가지 거리중 가장 큰 값을 비출 수 있는 가로등의 최소 높이를 구할 것이다.

이때 거리를 구할때 가로등과 가로등 사이의 거리가 홀수인 경우에는 가로등 사이 거리를 구해 나누기 2를 해준 값에서 +1을 해주어야 한다.

📌 코드 설계하기

1. n,m,locate를 입력받는다.
2. height를 0으로 초기화 한다.
3. height의 값을 가로등이 없는곳에서 첫번째 가로등까지의 거리로 초기화 한다.
4. 가로등과의 거리중 가장 긴 거리를 비출 수 있는 높이로 height를 업데이트 한다.
5. 마지막 가로등과 마지막 길까지의 거리와 현재 가로등 높이와 비교하여 비출 수 있는 가장 작은 높이로 업데이트 한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (8%)
   가로등 사이의 거리가 홀수인 경우 내림이 발생하여 빈곳이 발생함

📌 정답 코드

n = int(input()) #굴다리 길이
m = int(input()) #가로등 개수
locate = list(map(int, input().split())) #가로등 위치

#가로등 높이
height = 0

height = max(height, locate[0])
for i in range(1,m):
    if (locate[i]-locate[i-1]) % 2 == 0:
        height = max(height, (locate[i] - locate[i-1])//2)
    else:
        height = max(height, (locate[i] - locate[i-1])//2+1)
height = max(height, n - locate[-1])

print(height)