백준 2110 풀이 (공유기 설치, 이분 탐색)

진짜 주우우우우ㄹㄹㄹ라라라아아아아ㅏ아아 어려웠다. 맨날 힙합들으면서 풀다보니 집중도가 낮은 편이었는데 이번 문제는 도저히 머리가 안돌아가서 뉴에이지 들으면서 풀었다. 혼자 푼건 아니고 다른 고수들의 풀이를 참고했다.

 

우선 문제를 잘 읽어야 한다. 여기 보면 가장 인접한 두 공유기 사이의 거리를 가능한 크게 한다고 적혀있다.

이게 도대체 무슨 소리인가 고민을 해보면 그냥 적당히 띄어 두겠다라는 소리같다. 그럼 이걸 어떻게 구하는가?

예제를 보자 [1,2,4,8,9]의 위치에 집이 존재하기 때문에 공유기를 설치 가능하다. 그렇다면 공유기를 설치할 수 있는 경우의 수는 5C3이다. 10개의 경우의 수가 존재한다. 거기에 공유기가 3개이기 때문에 루프를 돌면서 3번씩 돌아서 최댓값을 찾는다고 가정하면 굉장히 많은 연산을 필요로 한다. 

대강 시간 복잡도를 생각해보면 (nCc * c) 가 될거다. 근데 n과 c가 큰 값이기 때문에 불가능하게 보인다.

 

그래서 대강 어떤 흐름인지 싶기때문에 조합에 따라 최댓값이 어떻게 나오나 그려본다.

대강 그려본 저 그림을 보면 조합에 따라 최댓값이 다르게 나오는 것을 확인가능하다. 그럼 최댓값을 기준으로 공유기의 위치를 지정하는 것은 어떨지 생각해본다.

 

그럼 최댓값을 한번 지정해 보고 어떤식으로 식으로 흐름이 진행될지 적어보자.

우선 1에 공유기를 설치하고 2에 공유기를 설치한다고 가정하면 거리가 1이기 때문에 설치 불가능하다.

다음 1에 공유기를 설치하고 4에 공유기를 설치한다고 가정하면 거리가 3이기 때문에 설치 불가능하다. 

다음 1에 공유기를 설치하고 8에 공유기를 설치한다고 가정하면 거리가 7이기 때문에 설치 가능하다.

(9는 할 필요가 없다. 왜냐하면 8을 기준으로 9까지의 거리가 1이기 때문에 거리가 4를 넘지 않아 공유기가 설치 불가능하다.)

그럼 루프를 다 돌았으나 공유기를 2개 밖에 설치할 수 없어서 최대값이 4이상일수가 없다.

그럼 최댓값은 1~3이 되는 것이다. 그렇다면 거리값을 기준으로 이분 탐색을 할 수 있을 거라는 가능성이 보인다.

 

그렇다면 거리의 최소값을 l, 최대값을 r로 두고 mid를 절반으로 설정하여 연산을 진행하면 이분탐색으로 거리의 최댓값을 구할 수 있다.

이러한 아이디어를 이용하여 코딩을 진행한다.

솔직히 처음에는 너무 어려웠고 다른 고수들의 답을 보아도 어떤흐름으로 진행되는건지 이해가 가지 않았다. 그래서 내 나름대로 이해한 방식을 풀이해 보았으니 누군가에게 도움이 되면 좋겠다.

import sys
n, c = map(int, input().split())
loc = []
for _ in range(n):
    loc.append(int(sys.stdin.readline()))
loc.sort()

l = 1
r = loc[-1]-loc[0]  #최대거리
mid = (l+r+1)//2

while l != r:
    # calc
    beforei = 0
    count = 1
    for i in range(1,n):
        if (loc[i] - loc[beforei]) >= mid:
            beforei = i
            count += 1
    if count >= c:
        l = mid
    else:
        r = mid - 1
    mid = (l+r+1)//2
print(mid)