본문 바로가기

개발자 강화/코딩 테스트

[백준] 17266 어두운 굴다리 / 이진탐색 / Python 실4

오랜만입니다. 아직 학부생이라 기말고사 공부하다 늦었음

 

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

 

가로등 높이만큼 왼쪽 오른쪽으로 빛이 퍼지는 데, 0~n 구간을 빠짐없이 빛으로 덮을 수 있는 최소 가로등 높이를 구해야 함

 

while문으로 이진탐색을 해야 풀리는 문제더라구요

 

left, right를 두고 역전되는 시점에 while문을 종료합니다

 

높이 h를 left right의 중간값으로 잡고,

현재 높이에서 커버 가능한 구간의 끝점을 잡아서 비교합니다

 

가로등 위치 for문을 돌면서

현재 커버 가능한 구간의 끝점을 가로등 위치+가로등 높이 h로 업데이트합니다

만약 커버 가능한 구간의 끝점이 가로등 위치 - 가로등 높이 h보다 작은 경우,

이전 가로등 커버 범위와 현재 가로등 커버 범위 사이에 공백이 발생한다는 의미 = 커버 불가, break

 

for문이 종료된 후, 커버 가능 구간의 끝점이 N보다 크거나 같으면 모든 구간이 덮였다는 의미

결과를 현재 가로등 높이로 업데이트한 후,

이보다 작은 경우도 가능한지 탐색하기 위해 right값에 mid-1을 대입합니다

 

만약 for문이 종료된 후에도 커버 가능 구간 끝점이 N보다 작다면 덮이지 않은 구간이 있다는 뜻이므려

left에 mid+1을 대입해 높이를 높입니다

 

def min_height_to_light(N, M, positions):
    # 이진 탐색을 위한 초기값
    left, right = 0, N
    result = N  # 최소 높이를 저장할 변수

    # 가로등 위치를 정렬
    positions.sort()

    while left <= right:
        mid = (left + right) // 2  # 높이 h를 중간값으로 설정
        current_coverage = 0  # 현재 덮인 구간의 끝

        for pos in positions:
            if current_coverage < pos - mid:
                # 현재 구간이 덮이지 않음
                break
            current_coverage = pos + mid

        if current_coverage >= N:
            # 모든 구간이 덮였다면 높이를 줄여본다
            result = mid
            right = mid - 1
        else:
            # 덮이지 않았다면 높이를 늘려야 함
            left = mid + 1

    return result

N = int(input())
M = int(input())
positions = list(map(int,input().split()))
print(min_height_to_light(N, M, positions))  # 결과: 최소 높이