[Baekjoon Online Judge] 백준 2110번 공유기 설치(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2110번 공유기 설치

(Python)

(글쓴날 : 2020.04.07)

 

---

* Baekjoon Online Judge, 백준 2110번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2110번 공유기 설치

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

---

2) 풀이 과정

수직선상에 집들의 위치가 주어지고, 주어진 집들 중 C개의 공유기를 N개의 집에 설치할 때, 가장 인접한 두 공유기 사이 거리의 최댓값을 구하는 문제입니다.

 

저의 경우, 이분 탐색 중 파라메트릭 서치를 적용하였으며, 중간값을 두 공유기 사이의 최댓값으로 설정했고,

그렇게 첫 번째 집부터 공유기를 설치해 나갈 때, 공유기를 C개만큼 설치할 수 있는지의 가능 여부에 따라 탐색을 하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N, C = map(int, input().split())
x = sorted([int(input()) for _ in range(N)])
result = 0
left = 0
right = max(x)
 
while left <= right:
    jump = mid = (left + right) // 2
 
    if mid * C > max(x):
        right = mid - 1
        continue
    
    count = 1
    interval = x[0] + jump
    for i in range(1, len(x)):
        if interval > x[i]:
            continue
        else:
            interval = x[i] + jump
            count += 1
    
    if count < C:
        right = mid - 1
    else:
        result = mid
        left = mid + 1
        
print(result)

---