[Python] 백준 #2110- 공유기 설치

문제

---

 

2110번: 공유기 설치

코드

---

 

Another answer

import sys
input = sys.stdin.readline

N, C = map(int,input().split())
array = [int(input()) for _ in range(N)]
array.sort() 

start = 1 
end = array[-1] - array[0]
answer = 0

while start <= end :
    now = array[0]
    cnt = 1 
    mid = (start+end) // 2
    for i in range(1,N) :
        if (array[i] - now >= mid ) :
            cnt += 1
            now = array[i]
    if cnt >= C :
        if answer < mid : 
            answer = mid
        start = mid + 1
    else :
        end = mid - 1

print(answer)

풀이

---

이번 문제도 역시 어떤 것을 중심으로 이분탐색을 진행해야할지가 아무리 생각해도 떠오르지 않았다. 해결 방법은 인접한 공유기의 최소거리를 mid로 설정하며 바꿔가며 진행해야 하는 것이었다.. 

우선 이분탐색의 두 start, end를 정하기위해서 살펴보면 두 공유기 사이의 최소 거리는 1, 최대 거리는 마지막 집과 처음 집사이의 거리가 된다. 이후 mid를 변경해가면서, 현재 집의 위치 now를 변경해가면서 현재 집과 다음 집의 거리가 mid이상이면 공유기를 설치한다. 이후 최종 설치된 공유기의 개수가 c이하면 구간을 변경해가며 진행한다. 

이후 공유기 한개에서  다른 집들을 돌면서 현재 집까지와의 거리를 계산한다.

 

말로해서는 어려우니 진행과정을 보면서 설명해보자.(코드와 같이 보는 것을 추천합니다.)

백준의 예시처럼 공유기의 개수 c=3, 집은 1,2,4,8,9에 위치해있다고 하자.

우선 이분탐색을 진행하기위해 집의 위치를 sort하고 수행하며, now와 cnt는 매 이분탐색마다 초기화된다. 

 

[첫 번째 이분탐색]
1. start = 1, end = 8, mid = 4, now= 1(첫번째 집), cnt = 1(설치된 공유기)
 array[1]-now = 2 - 1 = 1 < 4(mid) : 설치불가
-> 두 번째 집의 위치와 첫번째 집사이의 거리가 mid보다 작으므로, 설치할 수 없음.
왜냐면 mid는 두 인접한 공유기 사이의 최소거리를 의미하기 때문. 
array[2] - now = 4 - 1 = 3 < 4(mid) : 설치불가
array[3] - now = 8 - 1 = 7 > 4(mid) : 설치가능, cnt = 2, now = array[3] = 8
-> 네번째 집과 첫번째 집사이의 거리가 7로 설치가능하게 됨. cnt와 now 갱신해줬음.
array[4] - now = 9 - 8 = 1 < 4(mid): 설치불가

최종적으로 2(설치된 공유기의 개수,cnt) < 3(공유기 개수, 3) : 최소 거리 mid를 줄여야함 ->  end=mid-1
[두 번째 이분탐색]
2. start = 1, end = 3, mid = 2, now = 1, cnt = 1
array[1] - now = 2 - 1 = 1 < 2(mid) : 설치불가
array[2] - now = 4 - 1 = 3 > 2(mid) : 설치가능, cnt = 2, now = array[2] = 4
array[3] - now = 8 - 4 = 4 > 2(mid): 설치가능, cnt = 3, now = array[3] = 8
array[4] - now = 9 - 8 = 1 < 2(mid): 설치불가

최종적으로 cnt: 3 = c: 3  이기 때문에 answer = 2, start = mid + 1 
[세 번째 이분탐색]
3. start=3, end = 3, mid = 3, now =1, cnt = 1
array[1] - now = 2 - 1 = 1 < 3(mid): 설치불가
array[2] - now = 4 - 1 = 3 = 3(mid): 설치가능, cnt = 2, now = array[2] = 4
array[3] - now = 8 - 4 = 4 > 3(mid): 설치가능, cnt = 3, now = array[3] = 8
array[4] - now = 9 - 8 = 1 < 3(mid): 설치불가 

최종적으로 cnt: 3= c:3: 이기 때문에 answer = 3으로 갱신, start = mid +1

 

이런방식으로 진행하면 최종적으로 answer = 3이 된다. 

 

이분 탐색을 뭘로 진행할지를 잘 캐치하고, 조건들을 확인해야할 것 같다...