[백준] 어두운 굴다리 - 파이썬 Python

https://www.acmicpc.net/problem/17266

 

어두운 부분이 없도록 하는 최소한의 가로등 높이를 구한다.

개념: 이분탐색

 

이분탐색으로 가로등 높이를 탐색하려고 생각했는데, 특정 가로등 높이로 굴다리 전체를 밝힐 수 있는지 판별하는 함수를 구현하는데 오래 걸렸다.

1. start = 1, end = N으로 설정해서 가로등 높이를 탐색한다.
2. checkLight 함수는 특정 가로등 높이로 굴다리 전체를 밝힐 수 있는지 판단하는 함수다.
   • prev 변수는 마지막으로 밝혀진 위치이다.
   • 가로등 위치를 순회한다.
     
     • 현재 가로등 위치에서 높이를 뺀 값이 prev보다 크면, 이전 가로등과 현재 가로등 사이에 어두운 부분이 있다는 뜻이다. 따라서 False를 반환한다.
     • 그렇지 않으면, prev를 현재 가로등이 비추는 가장 먼 위치로 업데이트한다. (p + height)
   • 모든 가로등 위치를 확인한 후, 마지막으로 비춰진 위치가 굴다리 끝까지 도달했는지 확인하여 결과를 리턴한다.

n=int(input()) #굴다리 길이
m=int(input()) #가로등 개수
positions=list(map(int, input().split())) #설치할 수 있는 위치(오름차순)
start, end = 1, n
min_height=0

def checkLight(height):
    prev = 0 #마지막으로 밝혀진 위치
    for p in positions:
        if p - height > prev:
            return False
        else:
            prev = p + height
    return prev >= n
    
while start<=end:
    mid = (start+end)//2
    
    if checkLight(mid):
        end = mid - 1
        min_height = mid
    else:
        start=mid+1
        
print(min_height)

 

다른 접근..?

 

어쨌든 굴다리 모든 구석을 밝히기 위한 최소한의 가로등 높이(=가로 간격)를 구하는거니까, "간격"의 최대값을 구한다고 생각한다.

1. min_lamp_height 함수
   • 굴다리 시작 위치 ~ 첫 번째 가로등 위치 사이 간격을 max_gap과 비교하여 더 큰 값을 저장한다.
   • 마지막 가로등 위치 ~ 굴다리 끝 위치 사이 간격을 max_gap과 비교하여 더 큰 값을 저장한다.
   • 가로등 사이 간격 확인
     • 가로등 사이 간격의 절반(올림)을 max_gap과 비교하여 더 큰 값을 저장한다.
   • max_gap 값을 리턴한다. 이는 결국 필요한 가로등 높이의 최소값이다.

이렇게 하면 모든 지점이 빛에 의해 커버되는 최소한의 높이를 구할 수 있다.

N = int(input()) #굴다리 길이
M = int(input()) #가로등 개수
positions = list(map(int, input().split()))

def min_lamp_height(N, M, positions):
    # 최대 간격 초기화
    max_gap = 0
    
    # 첫 번째 가로등과 굴다리 시작점 사이의 거리
    max_gap = max(max_gap, positions[0] - 0)
    
    # 마지막 가로등과 굴다리 끝점 사이의 거리
    max_gap = max(max_gap, N - positions[-1])
    
    # 가로등 사이의 간격 확인
    for i in range(1, M):
        gap = positions[i] - positions[i-1]
        max_gap = max(max_gap, (gap + 1) // 2)
    
    return max_gap

result = min_lamp_height(N, M, positions)
print(result)