백준 2110번 : 공유기 설치

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

2110번: 공유기 설치

우아한 테크코스 코딩테스트를 준비할겸 기초 알고리즘을 복습하기 위해 접했던 이분 탐색 문제다.

기존에 풀었던 이분 탐색 문제와 달리 바로 해결 아이디어가 떠오르지 않아서 질문 게시판을 참고해서 해결했다.

 

 일직선(1차원) 좌표상의 특정 좌표에 집이 존재하고 주어진 개수만큼의 공유기를 집에 설치하고자 한다. 공유기는 한 집에 1개만 설치가능하며 주어진 개수만큼 공유기를 모두 설치했을때 공유기가 설치된 집들 중 사이 거리가 가장 작은 거리를 최대화하는 문제이다.

 

 질문을 올렸던 많은 사람들과 마찬가지로 나도 설치해야하는 공유기의 개수로 인해 고민을 많이했다. 최적화 문제이기에 이분 탐색을 통해 어떤 조건( f(x) )을 만족하는 적절한 값(x)을 찾아야 한다는 사실은 알고 있었지만, 어떤 값을 기준으로 어떤 조건을 세워야 하는지 막막했다. 급기야 공유기의 개수만큼 뽑는 조합을 모두 구해서 최대 거리를 계산하려는 생각까지했다.

 

 문제에서 최적화 해야하는 값은 결국 거리이다. 거리값을 기준으로 조건을 만족하는지 봐야한다. 여기서 나는 거리값이 집과 집 사이의 상대적인 값인데 최소한 두 집의 좌표가 결정되어야 한다는 생각에 빠져서 거리값을 비교하는게 아니라고 판단했다. 사실은 가능한 범위 내의 거리값들 중에서 공유기를 주어진 개수만큼 설치할 수 있는지를 판단하면 되는 문제였다.

 

 첫 거리값을 설정한 뒤에 첫번째 집부터 그 거리값 이상의 간격으로 떨어져 있는 집마다 공유기를 설치한다. 설치해야하는 공유기 수(c)와 비교해서 만약 더 설치해야한다면 거리값을 감소시키고 더 설치했다면 거리값을 증가시킨다. 첫번째 집부터 공유기를 설치하는 이유는 첫번째 집부터 특정 거리를 간격으로 설치했을때 설치 공유기 개수(c)를 만족시키지 못했다면, 어떤 임의의 집을 정해서 공유기를 설치 하더라도 해당 거리 간격으로는 절대 조건을 만족시키지 못하기 때문이다.

감사하게도 아래 링크에 관련된 내용을 어느 분이 친절하게 설명해주셨다.

https://www.acmicpc.net/board/view/31633

 

 작성한 정답 코드만 보면 흔하디 흔한 이분 탐색 문제와 다를 것이 전~~~혀 없지만 문제를 읽고 이분 탐색이라는 개념을 적용시키기 위해 생각하는 과정이 조금 어려웠다. 이런 식으로도 이분 탐색 알고리즘을 적용할 수 있다는 걸 깨달았고, 이 문제로 인해 이분 탐색 알고리즘의 개념을 더 명확하게 알게 된 것 같다. (질문 게시판에 있는 알고리즘 고인물분들의 도움을 많이 받았다.)

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
h = sorted([int(input()) for _ in range(n)])
s, e, m, r = 1, h[-1], 0, 0
while s <= e:
    m = (s+e) // 2
    now = h[0]
    cnt = 1

    for i in h:
        if now+m <= i:
            now = i
            cnt += 1

    if cnt >= c:
        s = m+1
        r = m
    else:
        e = m-1
print(r)