[백준/파이썬] 17266

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

실버 4 어두운 굴다리

 

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

def check(H, N, M, x):
    last = 0

    for i in range(M):
        left = x[i] - H
        right = x[i] + H

        if left > last:
            return False
        
        last = right
        if last >= N:
            return True


def binary(N, M, x):
    left, right = 1, N
    ans = N

    while left <= right:
        mid = (left + right) // 2

        if check(mid, N, M, x):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans            

N = int(input())
M = int(input())
x = list(map(int, input().split()))

min_height = binary(N, M, x)
print(min_height)

 

check 함수: 현재 높이 H로 굴다리 길이 N을 모두 밝힐 수 있는지 검사

last

마지막으로 밝혀진 위치

left = x[i] - H

현재 가로등이 비추는 왼쪽 경계

right = x[i] + H

현재 가로등이 비추는 오른쪽 경계

if left > last: return False

가로등이 못 비춰 어두운 구간 발생

해당 H 불가

last = right

오른쪽으로 밝혀진 위치 갱신

if last >= N: return True

굴다리 끝까지 밝힐 수 있으므로 True 반환

 

binary 함수: 이진 탐색을 통해 최소한의 가로등 높이 H 찾음

left, right = 1, N

최소 높이(left)는 1, 최대 높이(right)는 N

ans = N

정답을 저장할 변수이자 base

mid = (left + right) // 2

중간값을 높이로 설정

mid: 현재 검사할 가로등 높이

if check(mid, N, M, x):
    ans = mid
    right = mid - 1

check 함수로 체크해봤을 때 현재 mid 높이로 전부 비출 수 있다면

ans = mid

최소 높이 갱신

right = mid - 1

더 작은 높이가 가능한지 확인

else:
    left = mid + 1

현재 mid 높이로 불가능하다면

left = mid + 1

현재 높이로 부족하므로 높이를 증가

return ans

이진 탐색 종료 후 ans 반환