백준[ 17266 | Python ] 어두운 굴다리

문제

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

풀이

먼저 다리 0 부터 첫번째 가로등의 위치를 최초 높이로 잡아둔다.
그 다음 부터의 가로등의 높이는 가로등 1과 가로등 2 사이의 거리로 결정된다.
(가로등은 다리 양쪽으로 height 만큼 비추기 때문에 가로등의 높이는 (가로등 1 - 가로등 2) // 2)가 된다.

여기서 주의할 점은 그 사이의 거리가 홀수 일 때 양 쪽 가로등으로 비추지 못하는 공간이 하나 생기기 때문에 그 공간을 메워줄 1을 더해줘야한다는 점이다.

마지막은 for문 안에서 비교할 수 없기 때문에 마지막 가로등과 n사이의 거리를 마지막으로 갱신해준다.

n = int(input())
m = int(input())
lights = list(map(int, input().split()))
last,heights = lights[0],lights[0]

for i in range(1,len(lights)):
    tmp = abs(last-lights[i])
    
    if tmp % 2 == 0:
        tmp = tmp//2
    else:
        tmp = (tmp//2) + 1  

    heights = max(heights, tmp)

    last = lights[i]

heights = max(heights, abs(n-lights[len(lights)-1]))

print(heights)

생각 & 정리

이 문제에 어떻게 이분탐색을 적용시켜야 할 지 (특히 범위를 무엇으로 잡아야할지 도통 감이 안왔다.)
애매해서 이분탐색 문제이지만 이분탐색으로 풀지 않았다.

아래는 다른 분의 이분탐색으로 해결한 코드이다.

def bs(li, m):
    if li[1]-li[0] > m:
        return 0
    if li[-1]-li[-2] > m:
        return 0
    for i in range(1, len(li)-2):
        if (li[i+1]-li[i])/2 > m:
            return 0
    return 1

N, M = int(input()), int(input())
li = [0] + list(map(int, input().split())) + [N]
s, e = 0, N
res = 0
while s <= e:
    m = (s+e)//2
    if bs(li, m):
        e = m-1
        res = m
    else:
        s = m+1
print(res)

어떻게 이분탐색으로 사용할지 애매했던 가로등의 위치를 끝 점과 마지막점을 따로 넣어줘서 해결하신 것 같다.

참고 블로그 - https://jinho-study.tistory.com/956