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

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

17266번: 어두운 굴다리

 

 

풀이

사용한 알고리즘 : 라인 스위핑

 

풀이 전략

1. 맨처음 시작 위치인 0과 첫 가로등 사이의 거리를 구한다.

2. 각 각로등 사이의 거리를 구하되 짝수 거리만큼 떨어져 있으면 나누기 2한 몫을,

   홀수 거리만큼 떨어져 있으면 나누기 2한 몫에 1을 더한 값들 중 가장 큰 값을 저장한다.

3. 마지막 가로등의 위치와 굴다리 맨 마지막 위치 사이의 거리를 구한다.

4. 1~3번에서 구한 값들 중 가장 큰 값을 출력한다.

import sys

input=sys.stdin.readline

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

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

start=0
end=pos[0]
distance=end-start
pos.pop(0)

for i in pos:
    start=end
    end=i

    if (end-start)%2==1:
        if distance<int((end-start)/2)+1:
            distance=int((end-start)/2)+1
    else:
        if distance<int((end-start)/2):
            distance=int((end-start)/2)


if distance<N-end:
    distance=N-end

print(distance)