백준 17266 어두운 굴다리 Python

🐸 문제 정보

17266번: 어두운 굴다리

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

29.04m

 

📝 풀이

실버 4 문제였음에도 초반에 구현 방법을 잘못 설정하여 시간이 오래 걸렸다.

왼쪽 가로등과 비교하는 형식으로 구현했다가, 이렇게 되면 오른쪽 가로등과의 최적의 길이를 구할 수 없었다.

고친 풀이 방법은 아래와 같다.

 

1. 가로등 시작 위치와 끝 위치는 각각 0과 m과 차이를 비교해야함
2. 두 번째 가로등부터는 이전 가로등과 사이의 중간 값을 올림하여, 현재 저장된 가로등과 최대값으로 갱신

 

🧑‍💻 나의 답

# pypy3

import sys
import math
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
x = list(map(int, input().rstrip().split()))

res = x[0]
for i in range(1, m):
    res = max(res, math.ceil((x[i] - x[i - 1]) / 2))
res = max(res, n - x[-1])

print(res)