[백준, 파이썬, 17266번] 어두운 굴다리

 

풀이

• 처음 접근한 방법은 height를 하나씩 높혀가며 visit를 활용해서 해당 범위를 채우는 풀이로 접근
  • 해당 방법은 알 수 없는 while 루프에 빠져서 인지 7%에서 계속 맴돌게 되는 현상 발생...
• 이후 다른 접근 방법을 생각
  • 가로등 사이의 거리에 따른 범위, 즉 가로등 간의 거리 차를 구한 다음 
  • 해당 거리를 각각의 가로등이 같이 채우는 곳이 없도록 //2를 해주기!
    • 단 차이가 홀 수의 경우 하나의 빈 공간이 생기기에 +1 해주기
  • 그리고 사이의 가로등이 아닌 양 끝에 해당하는 가로등의 경우
    
    • 시작 가로등의 경우엔 해당 가로등의 위치에서 시작 위치까지 모두 비춰야하기에
      • if i == 0: result = max(li[i], result)  해당 코드를 적용
    • 마지막 가로등의 경우엔 마지막 거리에서 현재 가로등의 거리만큼 채워져야 하기에
      • elif i == m-1: result = max(n-li[i], result) 해당 코드를 적용
  • 마지막으로 단 하나의 가로등이 있을 경우
    • 현재 가로등 위치에서 양 끝의 위치를 다 비춰야 하기에
    • if m == 1: result = max(li[0], n-li[0])   해당 코드를 적용
    • 위에서 li[0] 만 적은 이유는 li[0] - 0으로 하면 시작 위치와의 차이를 구할 수 있는데
    • 굳이 -0을 할 필요가 없기 때문.

 

import sys

input = sys.stdin.readline

n = int(input())

m = int(input())

li = list(map(int,input().rstrip('\n').split()))

result = 0

if m == 1: result = max(li[0], n-li[0])

else:

    for i in range(m):

        if i == 0: result = max(li[i], result)

        elif i == m-1: result = max(n-li[i], result)

        else:

            _dif = li[i]-li[i-1]

            if not _dif%2: result = max(_dif//2, result)

            else: result = max(_dif//2+1, result)

print(result)