[백준] 17266 : 어두운 굴다리 (파이썬)

이진탐색 문제

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

---

💡 풀이코드 (성공) 

import sys 
import math 

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
light = list(map(int, sys.stdin.readline().split()))

def binary_search(maxNum):
    left = 0
    right = N
    answer = 0

    while left <= right:
        mid = (left + right) // 2
        
        if maxNum <= mid:
            right = mid - 1
            answer = mid 
        else:
            left = mid + 1
    print(answer)

maxNum = max(light[0] - 0, N - light[len(light) - 1])
for i in range(1, len(light)):
    diff = math.ceil((light[i] - light[i - 1]) / 2)
    maxNum = max(diff, maxNum)

binary_search(maxNum)

mid = 길을 모두 비추기 위한 가로등의 최소 높이

 

주요 로직

가로등이 비춰야 하는 거리 확인1 (시작-가로등, 가로등-끝)

입력으로 배열에 가로등의 위치(x)만 들어간다. 그런데, 가로등-가로등 사이의 간격보다 길의 시작 위치-가로등 혹은 가로등-길의 끝나는 위치 사이의 간격이 더 클 수 있으므로 maxNum이란 변수를 만들어 이 둘 중 max 값을 기록해준다.

maxNum = max(light[0] - 0, N - light[len(light) - 1])

---

가로등이 비춰야 하는 거리 확인2 (가로등-가로등)

가로등의 위치를 기록한 light 배열에서 for문을 돈다.

• 가로등-가로등 사이의 간격을 2로 나눈값을 올림해준다. 2로 나눠주는 이유는 왼쪽의 가로등과 오른쪽의 가로등이 반반 나눠 길을 비출 수 있기 때문이다. 
  
  • 가로등-가로등 간격이 짝수일 때 : 예) 2 4 -> 각각 반절(1)씩 길을 비추면 됨.
  • 가로등-가로등 간격이 홀수일 때 : 예) 2 5 -> 하나는 1만큼 길을 비추더라도 나머지는 2만큼 길을 비춰줘야함.
• 길의 시작 위치-가로등 혹은 가로등-길의 끝나는 위치 혹은 가로등-가로등에서 가로등이 길을 비춰야 하는 거리의 최댓값을 maxNum에 기록한다.

for i in range(1, len(light)):
    diff = math.ceil((light[i] - light[i - 1]) / 2)
    maxNum = max(diff, maxNum)

---

이진탐색

• 만약, 이진탐색으로 찾은 가로등의 최소 높이가 가로등이 길을 비춰야 하는 거리의 최댓값보다 크다면 가로등의 최소 높이를 너무 크게 설정한 것이다. 따라서, right = mid - 1로 설정하여 더 작은 mid값을 가지고 길을 모두 비출 수 있는지 확인해야 한다.
• 만약, 이진탐색으로 찾은 가로등의 최소 높이가 가로등이 길을 비춰야 하는 거리의 최댓값보다 작다면 가로등의 최소 높이를 너무 작게 설정한 것이다. 따라서, start = mid + 1로 설정하여 더 큰 mid값을 가지고 길을 모두 비출 수 있는지 다시 확인해야 한다.

if maxNum <= mid:
    right = mid - 1
    answer = mid 
else:
    left = mid + 1