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

 

문제 분석

• 굴다리의 모든 길 N
• 가로등 설치 개수 m, 각 가로등 위치 x
• 각 가로등은 높이만큼 주위를 비칠 수 있다.
• 최소한의 높이로 굴다리 모든 길을 밝히려고 한다.
• 최소한의 가로등 높이를 구하라.
• 단, 가로등의 높이는 모두 같고 정수이다.

 

코드 설계

• 최소 높이
  • 맨 앞의 가로등과 시작 지점과의 차이
  • 가로등과 가로등 사이의 거리 중 최장 거리 // 2
  • 맨 끝의 가로등과 끝 지점의 차이
• 중 가장 긴 거리 출력

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input()) # 시작 위치 0, 끝 위치 n-1
m = int(input())
x = list(map(int, input().split()))

# 가로등 사이 거리 중 최장거리 찾기
longest = 0
for i in range(len(x)-1) :
    longest = max(longest, (x[i+1]-x[i]))

ans = max(x[0], (longest+1)//2, n-x[-1])
print(ans)