파이썬) 어두운 굴다리 -BOJ

 

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

17266번: 어두운 굴다리

 

import sys
input = sys.stdin.readline

n = int(input())

m = int(input())

position = list(map(int, input().split()))

answer = 0

if len(position) == 1:
    answer = max(position - 0, n - position)
else:

    for i in range(len(position)):
        if i == 0:
            height = position[i]

        elif i == len(position) - 1:
            height = n - position[i]
        else:
            t = position[i] - position[i-1]

            if t % 2 == 1:
                height = t // 2 + 1

            else:
                height = t // 2

        answer = max(height, answer)


print(answer)

이 문제는 이분탐색 문제지만 내가 1시간 넘게 고민하고 결국 풀지 못했던 문제이다.

먼저 for문을 살펴보자

만약 가로등이 첫번째 가로등이라면 무조건 0번까지 비추어야한다.

반대로 가로등이 마지막 가로등이라면 무조건 길 끝까지 비추어야한다

그 중간 값이라면 현재 가로등(position[i])와 내 전의 가로등의 사이를 구해 그 절반의 값이 현재 가로등이 비추어야 할 길이(가로등의 높이)이다.

만약 절반값이 홀수라면 그 두개의 가로등이 겹쳐져 비추어야하기 때문에 +1을 해준다.

저들 중 최대 값이 정답이다.