[백준/Python] 2110 공유기 설치

알고리즘 - 공유기 설치

Posted by Kyun2da on August 31, 2020

1️⃣ 서론

백준 문제 2110번 공유기 설치 입니다. 파이썬(Python)으로 풀었습니다.

2️⃣ 문제 설명

이 문제는 집 N개가 있다고 하면, 공유기 C개를 적절하게 가장 짧은 거리가 최대가 되게끔 푸는 문제입니다.

3️⃣ 풀이

이 문제는 이분탐색으로 해결할 수 있습니다.

바로 공유기의 가장짧은거리를 탐색하는 방법입니다.

즉, 거리를 임의로 정해 해당 거리로 공유기 C개를 모두 배치할수 있는지를 검사하며 답이 될 수 있는 가장 큰 거리를 찾는 문제입니다.

소스코드 보겠습니다.

4️⃣ 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys

n, c = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

# 집의 위치를 오름차순으로 정렬한다.
arr.sort()

# 가장 짧은 거리를 1이라고 하고 가장 큰거리를 첫집과 끝집의 차이라고 가정한다.
start = 1
end = arr[-1] - arr[0]

maxVal = 0
while start <= end:
    mid = (start + end) // 2
    idx, result = 0, 1
    # 집을 순회하며 공유기를 설치할 수 있는지의 여부를 검사한다.
    for i in range(1, len(arr)):
        if arr[idx] + mid <= arr[i]:
            result += 1
            idx = i
    # 만약 공유기를 전부 설치할 수 없다면 거리를 낮춘다.
    if result < c:
        end = mid - 1
    # 공유기를 전부 설치할 수 있다면 거리를 높인다.
    elif result >= c:
        maxVal = mid
        start = mid + 1

print(maxVal)

5️⃣ 마치며..

질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️