백준 17266 어두운 굴다리 (with Python)

어떤 문제?

백준 온라인 저지에 있는 17266번 문제 어두운 굴다리 입니다.

내가 작성한 Solution

이분 탐색으로 분류되는 문제지만, 이분 탐색으로 풀 자신이 없어서 생각나는 방법으로 풀었습니다.

문제에서 생각해볼 점

• 주어진 가로등의 위치에서 맨 처음 가로등은 굴다리 입구까지 완벽하게 빛을 비춰줘야 합니다.

• 마찬가지로 맨 마지막 가로등은 굴다리가 끝나는 지점까지 완벽하게 빛을 비춰줘야 합니다.

• 양쪽 끝을 제외한 가로등은 옆의 가로등과의 거리 절반 만큼 빛을 비춰주면 됩니다.

• 이해하기 쉽도록 그림을 그렸는데 아래와 같습니다.
  

• 그럼 결국 가장 넓은 범위를 비춰주는 가로등을 찾으면 되는 문제입니다.

• 코드는 아래와 같습니다.

코드 구현

• 가로등이 하나 있을때는 가로등을 기준으로 굴다리 입구쪽 까지의 거리와 끝나는 지점 까지의 거리중 하나를 선택하면 됩니다.

N = int(input())
M = int(input())

positions = list(map(int, input().split()))
len_positions = len(positions)

min_height = 0

# 가로등이 하나 있는 경우
if len_positions == 1:
    min_height = max(positions[0] - 0, N - positions[0])
# 가로등이 하나 이상인 경우
else:
    for i in range(len_positions):
        # 입구 근처의 첫번째 가로등이 비춰줘야할 거리
        if i == 0:
            height = positions[i] - 0
        # 끝나는 지점 기준 가장 가까운 가로등이 비춰줘야할 거리
        elif i == len_positions - 1:
            height = N - positions[i]
        # 양 끝의 가로등을 제외한 가로등
        else:
            tmp = positions[i] - positions[i-1]
            if tmp % 2:
                height = tmp // 2 + 1
            else:
                height = tmp // 2
        # 가장 큰 범위를 찾으면 되니까 max로 갱신
        min_height = max(height, min_height)

print(min_height)