[Python - Binary Search] 2110 공유기 설치

📌 문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x₁, ..., x_N이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

 

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

 

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 x_i (0 ≤ x_i ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

📌 출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

📌 문제 풀이

👨‍🏫 접근

이걸 처음 보고 이진탐색이다! 라고 생각하기가 너무 어려웠다. 아직 어떤 알고리즘을 써야 하는지 판단하는 능력이 필요한 것 같다. 일단 보면 최댓값을 구해야 한다. 최댓값을 구하는 알고리즘은 보통 다이나믹 프로그래밍이나 백트래킹, 이진탐색 등을 사용한다. 그런데 다이나믹 프로그래밍을 하자기에는 알고리즘이 세워지지 않고, 백트래킹을 하기에는 N과 x가 작지 않은 편이었다. 그래서 이진탐색을 쓰지 않았을까 싶기도 하다.

 

그리고 문제에서 중요한 것은 "거리" 이 한 가지 값이다. 그렇기 때문에 이진 탐색이 적합할 것이다. 거리라는 한 가지 변수가 있고, 그 변수로 리스트를 순회하면서 값을 구하도록 한다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys

n, c = map(int, sys.stdin.readline().split())
x = sorted(map(int, sys.stdin.readlines()))

# 거리를 이진탐색으로 정하고, for문으로 0 인덱스로부터 검사하기 시작.
# 만약 검사하면서 가능한 경우가 c보다 작으면 거리를 줄임
# 가능한 경우가 c보다 크다면 거리를 넓힘(이때 ans 저장)

pl, pr = 1, x[-1] - x[0]
dist = 0

while pl <= pr:
    mid = (pl + pr) // 2
    standard = x[0]
    available = 1

    for i in range(1, n):
        if x[i] - standard >= mid:
            standard = x[i]
            available += 1

    if available >= c:
        dist = mid
        pl = mid + 1
    else:
        pr = mid - 1

print(dist)

📄 준비

import sys

n, c = map(int, sys.stdin.readline().split())
x = sorted(map(int, sys.stdin.readlines()))

# 거리를 이진탐색으로 정하고, for문으로 0 인덱스로부터 검사하기 시작.
# 만약 검사하면서 가능한 경우가 c보다 작으면 거리를 줄임
# 가능한 경우가 c보다 크다면 거리를 넓힘(이때 ans 저장)

pl, pr = 1, x[-1] - x[0]
dist = 0

먼저 배열을 정렬해준다. 이 문제에서는 각 공유기가 좌표로 정해져있기 때문에 순회를 위해서는 순서대로 돌아다녀야 한다. 게다가, 공유기 한 개는 처음 집의 좌표로 고정된다. 왜냐하면 첫 집으로부터 어떠한 집을 정하더라도 그 값이 다른 기준에 비해서 최솟값이 크기 때문이다. 예를 들어, 1-2-4-5의 좌표가 있고 공유기를 세 개 정한다고 하면, 1번 집을 미리 지정해두고 공유기를 설치하는 것과 2번 집을 지정하고 공유기를 설정하는 것만 봐도 1번 집이 기준이 되어 탐색하는 것이 효율적임을 추측해볼 수 있다.

 

pl이 0일 이유는 없어서 1로 정했다. 거리도 1부터 시작하기 때문이다. 최댓값인 pr은 가장 먼 거리를 인덱싱하여 저장했다. 처음에는 max로 구했었는데 이렇게 하면 시간 복잡도가 더 커지니까 위 방법이 더 낫다.

📄 풀이

while pl <= pr:
    mid = (pl + pr) // 2
    standard = x[0]
    available = 1

    for i in range(1, n):
        if x[i] - standard >= mid:
            standard = x[i]
            available += 1

    if available >= c:
        dist = mid
        pl = mid + 1
    else:
        pr = mid - 1

print(dist)

이진탐색으로 구할 것은 거리이다. 먼저 기준 거리를 pl, pr로 모의로 정한다.

 

그 다음 첫 집부터 순회한다. 그래서 standard 변수에 x[0] 값을 넣었다. 기준을 첫 번째 집으로 설정했으므로 일단 가능한 공유기가 1개이다.

 

두 번째 인덱스부터 탐색을 시작한다. 만약 기준으로 세운 집의 좌표와 순회하는 집의 좌표의 차이가 mid 값과 일치하거나 커야 공유기를 설치할 수 있으므로 그 조건에 따라 반복해준다. 그래서 조건을 만족하면, 카운트 한 곳의 집의 좌표를 기준으로 넣어서 다시 순회한다. 그리고 공유기를 설치할 수 있으므로 available 값을 1 늘린다.

 

그렇게 가능한 공유기의 개수가 원하는 c 값보다 크거나 같을 때, dist에 값을 넣어주고 거리를 넓혀 거리의 최댓값을 구하며 공유기의 개수와 일치하도록 해준다.

📌 총평

 

이진탐색에서 꽤 어려웠던 문제였다. 매개 변수를 어떻게 활용할지 잘 생각해내야 한다.