[백준] 2110 : 공유기 설치 (파이썬)

이분 탐색 문제

https://www.acmicpc.net/problem/2110

---

문제 이해

1. 요점

문제의 요점은 다음과 같다.

각 공유기 사이의 거리 및 간격이 최대가 되게끔 공유기 C개를 배치하라.

즉, 공유기 C개를 각각 최대한 멀리 떨어뜨려라.

이때 공유기 사이의 거리 및 간격이 각각 달라도 된다. 최대가 되게 공유기를 배치 후 이 중에서 최소값을 출력한다.

결론적으로는 공유기들이 각각 최대한 멀리 떨어져 있어야 한다.

 

2. 예시

9 3
1 2 3 4 5 6 7 8 100
정답 : 7 (1 8 100)

9 4
10 20 30 40 48 60 70 80 81
정답 : 20 (10 30 60 80)

9 4
1 2 3 4 5 6 7 15 100
정답 : 6 (1 7 15 100)


10 4
1 2 3 4 5 6 7 8 9 10
정답 : 3 (1 4 7 10)

 

---

접근 방식 

이분 탐색으로 최대가 될 수 있는 공유기 사이의 거리를 찾아보자.

• 공유기 C개를 설치하면서, 각각의 공유기 사이의 거리가 최대가 돼야 한다.

mid= 공유기 사이의 거리 (가장 인접한 공유기 사이의 거리) -> 최댓값으로 만드는게 목표

start = 공유기 사이의 최소 거리  = 1

end = 공유기 사이의 최대 거리  = arr[-1] - arr[0] (공유기 사이의 최대 거리는 가장 큰 공유기의 x좌표 - 가장 작은 공유기의 x좌표)

---

💡 풀이코드 (성공)

import sys 
N, C = map(int, sys.stdin.readline().split())
arr = []
for _ in range(N):
    arr.append(int(sys.stdin.readline().strip()))
arr.sort()

def binary_search(N, C, arr):
    start = 1 # 공유기 최소 거리
    end = arr[-1] - arr[0] # 공유기 최대 거리 -> 가장 큰 것과 가장 작은 것의 간격이 최대 간격임. 
    answer = 0

    while start <= end:
        cnt = 1
        last = arr[0] # debug : 위치 변경
        mid = (start + end) // 2 # 가장 인접한 공유기 간의 거리 -> 최댓값으로 만드는게 목표 

        for i in range(1, N): # 처음 공유기는 항상 선택 
            if arr[i] >= last + mid:
                last = arr[i]
                cnt += 1 
        
        if cnt >= C:
            start = mid + 1 
            answer = mid 
        else:
            end = mid - 1 

    return answer
    
print(binary_search(N, C, arr))

 

주요 로직

1. 지정한 mid(가장 인접한 공유기 간의 거리)로 공유기를 몇개 설치할 수 있는지 확인하기

• 처음 공유기는 항상 선택돼야 하므로 for문을 0을 제외하고 1 ~ N까지 돈다.
• mid는 현재 지정한 가장 인접한 공유기 간의 거리를 의미한다.
• 만약 현재 공유기의 좌표가 (마지막으로 선택한 공유기의 좌표 + 공유기 사이의 간격)보다 크다면 선택될 수 있으므로 cnt를 증가시켜준다.
  • 마지막으로 선택한 공유기의 좌표와 mid 이상의 간격으로 떨어져있다는 의미이므로 이번 i번째 공유기가 선택될 수 있다.

for i in range(1, N): # 처음 공유기는 항상 선택 
    if arr[i] >= last + mid:
        last = arr[i]
        cnt += 1

 

 

2. mid 간격으로 공유기를 설치했을 시의 설치 가능한 공유기 갯수를 비교하여 start / end값 조정하기 

• 만약 해당 mid 간격으로 공유기를 설치를 하였을 때, 설치할 수 있는 공유기의 갯수(cnt)가 C보다 크다면 공유기의 간격을 너무 작게 설치한 것이다. 따라서, start = mid + 1로 설정하여 더 큰 mid값을 가지고 설치할 수 있는 공유기의 갯수를 다시 확인해야 한다.
• 그렇지 않은 경우라면 즉, 설치할 수 있는 공유기의 갯수(cnt)가 C를 도달하지 못한다면 공유기의 간격을 너무 크게 설정한 것이다. 따라서, end = mid - 1로 설정하여 더 작은 mid값을 가지고 설치할 수 있는 공유기의 갯수를 다시 확인해야 한다.

if cnt >= C:
    start = mid + 1 
    answer = mid 
else:
    end = mid - 1

 

---

참고 문헌

https://hongcoding.tistory.com/3

[백준] 2110번 공유기 설치 (Python 파이썬)

https://velog.io/@yoonuk/%EB%B0%B1%EC%A4%80-2110-%EA%B3%B5%EC%9C%A0%EA%B8%B0-%EC%84%A4%EC%B9%98-Python

[백준] 2110: 공유기 설치 (Python)