알고리즘 문제

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

feelcoding 2020. 1. 18. 20:51
728x90

2019 인하대학교 프로그래밍 경진대회(IUPC) D번 문제

 

17266번: 어두운 굴다리

인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다. 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정이 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑

www.acmicpc.net

from sys import stdin
n = int(input())
m = int(input())
location = list(map(int, stdin.readline().split()))
gap = []
gap.append((location[0] - 0) * 2)
for i in range(1, m):
    gap.append(location[i] - location[i - 1])
gap.append((n - location[-1]) * 2)
a, b = divmod(max(gap), 2)
if b == 0:
    print(a)
else:
    print(a + 1)
728x90