[백준] 백준 python 2110번 문제 및 소스코드
2024. 10. 5. 13:51ㆍCoding/백준-Python
1. 문제 링크
https://www.acmicpc.net/problem/2110
2. 문제
3. 소스코드 및 설명
import sys
input = sys.stdin.readline #시간 초과 방지
# n: 집의 개수, c: 설치할 공유기 개수
n, c = map(int, input().split()) #입력받은 값을 공백으로 분리
#집의 위치를 리스트에 저장하고 정렬
houses = [int(input()) for i in range(n)]
houses.sort()
#start: 최소 간격(1), end: 최대 간격(집들 간의 최대 거리)
start = 1
end = houses[-1] - houses[0]
#이진 탐색을 통해 공유기를 설치할 수 있는 최대 간격을 찾는 함수
def binarySearch(houses, start, end):
while start <= end:
mid = (start + end) // 2 #중간값(현재 탐색하는 간격)
current = houses[0] #첫 번째 집에 공유기 설치
cnt = 1 #설치한 공유기 개수(첫 번째 집에 설치했기 때문에 1)
for i in range(1, n):
if houses[i] >= current + mid:
cnt += 1
current = houses[i]
#설치한 공유기 개수가 c 이상이면 간격을 더 늘려도 되므로 최소 간격인 start 값을 증가시킴
if cnt >= c:
start = mid + 1
result = mid #가능한 최대 간격을 저장
else:
end = mid - 1 #설치한 공유기 개수가 부족하면 간격을 줄인다
return result #최종적으로 찾은 최대 간격 반환
#최적의 최대 간격 출력
print(binarySearch(houses, start, end))
'Coding > 백준-Python' 카테고리의 다른 글
[백준] 백준 python3 1978번 문제 및 소스코드 (0) | 2024.10.08 |
---|---|
[백준] 백준 Python3 2166번 문제 및 소스코드 (0) | 2024.10.08 |
[백준] 백준 python 14725번 문제 및 소스코드 (0) | 2024.10.07 |
[백준] 백준 python 2293번 문제 및 소스코드 (1) | 2024.10.06 |
[백준] 백준 python 1759번 문제 및 소스코드 (0) | 2024.10.05 |