[알고리즘] 백준 파이썬 17266 어두운 굴다리

📍 문제 탐색하기어두운 굴다리 문제는 길이 N의 굴다리에서, 설치된 M개의 가로등이 굴다리 전체를 밝힐 수 있도록 최소한의 높이 HHH를 계산하는 문제이다.각 가로등은 높이HH만큼 주위를 밝힐 수 있으며, 모든 가로등의 높이는 동일해야 한다.문제 조건굴다리 길이 N: 1≤N≤100,000가로등 개수 M: 1≤M≤N가로등 위치 x: M개의 가로등 위치가 오름차순으로 주어진다.가로등의 높이 H: x에서 왼쪽으로 H, 오른쪽으로 H 범위를 밝힌다.출력 조건모든 구간(길이 0부터 N)이 밝아지도록 하는 최소 높이 H를 출력한다.입력 범위가로등 위치는 오름차순으로 주어짐.모든 가로등 높이는 동일해야 함.굴다리 길이가 크기 때문에, 선형 탐색 대신 이분 탐색이 필요하다.가능한 시간 복잡도이분 탐색: log⁡N가로..
알고리즘 2025. 1. 18. 22:51
1