[백준 Python] 2110 공유기 설치

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

2110번: 공유기 설치

문제정리

N 개의 집이 수직선 위에 있다. 중복X

C 개의 공유기를 설치한다.

이때 한 집에 하나만 설치하며 인접 설치 X 이다.

가장 인접한 공유기의 거리가 최대인 경우를 구해라

* (1, 2, 4) 는 불가 (2, 6, 8) 일 때는 output : 4

 

문제풀이

1. greedy 로 생각해 보자

N 개의 집에서 C 개를 뽑아 공유기를 설치해본다.

각각의 경우에 인접한지 판단하고 가장 가까운 거리를 찾는다.

그렇게 구한 가까운 거리들 중에 가장 큰 값을 구한다.

위 방법은 순열, 조합으로 구현할 수 있다.

# N 개 집 수직선 (좌표) 중복X
# C 개 공유기 설치
# 한집에 하나만, 인접한 공유기 거리 최대
# C 개의 공유기를 N 개에 적당히 설치

import sys
input = sys.stdin.readline
import itertools 

N,C = map(int,input().split())

arr = []
for i in range(N):
    arr.append(int(input()))
arr.sort()

ans = 0
for per in itertools.combinations(arr, C): # (1, 2, 4)

    min = 1000000000
    for i in range(0,C-1):
        temp = per[i+1] - per[i]
        
        if temp <= min:
            min = temp

    if min != 1 and ans <= min:
        ans = min

print(ans)

하지만 시간초과가 나온다.

 

2. 이분 탐색, 매개변수 탐색 (결정 탐색)

구하는 답 : 조건을 만족하는 거리

그 거리에 따라 C 개의 공유기를 설치 가능, 불가능이 나누어 지게 된다. > 매개변수 탐색 (결정 탐색)

이때 그 거리를 1 부터 최대 가능 거리까지 쭉 증가시키면서 찾으면 답은 나오긴 한다. ( 브루트 포스 )

하지만 그 거리를 이분 탐색으로 결정하여 시간을 줄일 수 있다.

 

공유기 사이의 거리를 기준으로 lo = 2, hi = arr[-1] - arr[0] 으로 두고 이분탐색을 진행한다.

이를 통해 mid = 거리 를 정하고 그 거리 이상일 때 공유기를 설치한다. 이때 설치한 공유기가 C 보다 많거나 같으면 거리를 늘려주고 적다면 거리를 줄여준다.

* 첫번째 집은 공유기를 무조건 설치하게 된다.

why? 간단하게 길이가 10 인 막대기에 N 개의 점이든 공유기든 설치한다고 생각해보자 맨 왼쪽이 아닌 2 좌표에 처음 점을 찍으면 결과적으로 길이가 8 인 막대기에 N 개를 배치하는 것으로 당연히 맨 왼쪽에 설치하는 것이 더 낫다는 것을 알 수 있다.

# N 개 집 수직선 (좌표) 중복X
# C 개 공유기 설치
# 한집에 하나만, 인접한 공유기 거리 최대
# C 개의 공유기를 N 개에 적당히 설치

import sys
input = sys.stdin.readline

N,C = map(int,input().split())

arr = []
for i in range(N):
    arr.append(int(input()))
arr.sort()

def judge(mid):
    cnt = 1
    current = arr[0] # 공유기 첫번째집 설치

    for i in range(1,len(arr)):
        if arr[i] >= current + mid: # 거리 기준으로 설치 가능
            current = arr[i] # 다음 집 설치
            cnt += 1
    if cnt >= C:
        return True
    else:
        return False

lo = 2
hi = arr[-1] - arr[0]
ans = 0
while lo <= hi:
    mid = (lo + hi) // 2
    if(judge(mid)):
        lo = mid + 1
    else:
        hi = mid - 1

print(hi)

 

참고 https://annajeong.github.io/algorithm/parametric/

[Algorithm] Binary Search와 Parametric Search