코딩 챌린지 13일차 : 17266번 어두운 굴다리(S4)

17266 : 어두운 굴다리 - 문제 링크

1. 문제 탐색하기

입력

n 굴다리의 길이
m 가로등의 개수
locations[m] 가로등의 위치

구하고자 하는 것

굴다리의 길이 n을 모두 비추기 위한 가로등의 최소 높이

알고리즘 설계

가로등 간격이 가장 넓은 곳에서 최대 높이가 필요함
최대 높이 = (가로등 사이의 거리 + 1) // 2
* python의 round는 오사오입이므로 round를 직접 구현

모든 가로등 사이의 거리를 계산하며 최대 높이를 갱신

양 끝의 가로등은 홀로 굴다리의 끝까지 비추어야 하기 때문에
가로등에서부터 굴다리 끝까지의 거리가 최대 높이가 되는데,
이 케이스도 같이 계산해야 함.

이분 탐색이 주제지만 시간 내에 통과할 수 있을 것으로 판단되어 브루트포스로 구현함..

시간복잡도

모든 가로등에 대해 탐색 -> $O(n)$
1 $\leq$ n $\leq$ 100,000이므로 시간 내에 통과 가능

2. 코드 설계하기

1. input 받기
2. 양 끝 가로등에 대해 먼저 최대 높이 계산
3. 모든 가로등 순회하며 최대 높이 갱신

3. 시도 회차 수정 사항

1회차) 시간 초과 없이 성공 :-)

4. 정답 코드

import sys
input = sys.stdin.readline

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

height = max(locations[0], n - locations[-1])
for i in range(m - 1):
    if (locations[i + 1] - locations[i] + 1) // 2 > height:
        height = (locations[i + 1] - locations[i] + 1) // 2

print(height)

이렇게 푸는 거 아닌 거 같은데 . . .

5. 해설지 참고 후

• 이분탐색으로 푸는 게 시간이 더 오래 걸리는데 굳이…?