반응형
https://www.acmicpc.net/problem/2110
N, C = map(int, input().split())
house = [int(input()) for _ in range(N)]
house.sort() # 오름차순 정렬
low, high = 1, house[-1] - house[0]
while low <= high:
mid = (low + high) // 2
cur = house[0] # 공유기를 설치한 마지막 위치
count = 1 # 설치한 공유기 개수
# 앞 집부터 공유기 설치
for i in range(1, N):
if house[i] >= cur + mid:
cur = house[i]
count += 1
if count >= C:
low = mid + 1
else:
high = mid - 1
print(high)
1. 필요한 정보를 입력받은 뒤 house를 오름차순 정렬한다.
2. 이분탐색을 한다.
2-1. mid를 구한 뒤 cur, count를 초기화한다.
2-2. 앞 집부터 공유기를 설치한다. 집의 좌표(house[i])가 cur + mid보다 크거나 같다면 공유기를 설치한다.
2-3. count > = C 인 경우 거리를 더 넓게 공유기를 설치할 수 있다는 것이므로 low = mid + 1
2-4. count < C 인 경우 거리를 줄여야하므로 high = mid - 1
3. 결과를 출력한다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
[백준/Python] 크게 만들기 (0) | 2021.12.06 |
---|---|
[백준/Python] 병든 나이트 (0) | 2021.12.02 |
[백준/Python] 녹색 옷 입은 애가 젤다지? (0) | 2021.11.24 |
[백준/Python] 스타트링크 (0) | 2021.11.21 |
[백준/Python] 최단경로 (0) | 2021.11.19 |