[Algorithm] 백준 #17266 어두운 굴다리

 

 

import sys
input = sys.stdin.readline

N = int(input())  # 굴다리 길이
M = int(input())  # 가로등 갯수
lights = list(map(int, input().split()))  # 설치 위치
heights = lights[0]  # 초기 높이는 첫번째 가로등 위치로

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

# 맨 마지막 가로등 비교
heights = max(heights, abs(N-lights[-1]))
print(heights)

 

 

 

• 가로등의 첫번째 위치를 초기 높이로 잡아준다
• 그 이후 가로등의 높이는 i-1번째 가로등, i번째 가로등의 거리로 결정된다
• 가로등은 양쪽으로 높이만큼 비추기에, 가로등 높이는 abs(i-1번째 가로등-i번째 가로등) // 2 가 된다.
• 마지막 N-가로등 위치는 for문 밖에서 비교해준다