오랜만입니다. 아직 학부생이라 기말고사 공부하다 늦었음
https://www.acmicpc.net/problem/17266
가로등 높이만큼 왼쪽 오른쪽으로 빛이 퍼지는 데, 0~n 구간을 빠짐없이 빛으로 덮을 수 있는 최소 가로등 높이를 구해야 함
while문으로 이진탐색을 해야 풀리는 문제더라구요
left, right를 두고 역전되는 시점에 while문을 종료합니다
높이 h를 left right의 중간값으로 잡고,
현재 높이에서 커버 가능한 구간의 끝점을 잡아서 비교합니다
가로등 위치 for문을 돌면서
현재 커버 가능한 구간의 끝점을 가로등 위치+가로등 높이 h로 업데이트합니다
만약 커버 가능한 구간의 끝점이 가로등 위치 - 가로등 높이 h보다 작은 경우,
이전 가로등 커버 범위와 현재 가로등 커버 범위 사이에 공백이 발생한다는 의미 = 커버 불가, break
for문이 종료된 후, 커버 가능 구간의 끝점이 N보다 크거나 같으면 모든 구간이 덮였다는 의미
결과를 현재 가로등 높이로 업데이트한 후,
이보다 작은 경우도 가능한지 탐색하기 위해 right값에 mid-1을 대입합니다
만약 for문이 종료된 후에도 커버 가능 구간 끝점이 N보다 작다면 덮이지 않은 구간이 있다는 뜻이므려
left에 mid+1을 대입해 높이를 높입니다
def min_height_to_light(N, M, positions):
# 이진 탐색을 위한 초기값
left, right = 0, N
result = N # 최소 높이를 저장할 변수
# 가로등 위치를 정렬
positions.sort()
while left <= right:
mid = (left + right) // 2 # 높이 h를 중간값으로 설정
current_coverage = 0 # 현재 덮인 구간의 끝
for pos in positions:
if current_coverage < pos - mid:
# 현재 구간이 덮이지 않음
break
current_coverage = pos + mid
if current_coverage >= N:
# 모든 구간이 덮였다면 높이를 줄여본다
result = mid
right = mid - 1
else:
# 덮이지 않았다면 높이를 늘려야 함
left = mid + 1
return result
N = int(input())
M = int(input())
positions = list(map(int,input().split()))
print(min_height_to_light(N, M, positions)) # 결과: 최소 높이
'개발자 강화 > 코딩 테스트' 카테고리의 다른 글
[백준] 22233 가희와 키워드 / 구현 / Python 실3 (0) | 2024.12.11 |
---|---|
[백준] 1522 문자열 교환 / 구현 / python 실1 (0) | 2024.12.04 |
[백준] 1283 단축키지정 / 구현 / Python 실1 (0) | 2024.12.03 |
[백준] 24037 문자열게임2 / 구현 / python 골5 (0) | 2024.12.02 |
[백준] 11501 주식 / 그리디 / python 실2 (0) | 2024.12.01 |