[코테] 공유기 설치

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

2110번: 공유기 설치

N개의 집의 개수에 c개의 공유기를 설치하는데 공유기간 거리를 최대로 하고싶을때 공유기간 거리중 최소치를 구하시오.

 

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

def check(m):
    temp = 0
    last =arr[0]
    for i in arr[1:]:
        if i>=last+m:
            last=i
            temp+=1
        if temp==c-1:
            return 1
            #m거리로 설치했는데 다설치했으면 가능
    return 0

ans = 0
s = 1
e = (arr[-1]-arr[0])//(c-1)
while s<=e:
    m = (s+e)//2
    if check(m):#설치가능,더늘려보자
        ans = m
        s = m+1
    else:#설치불가능,줄이자
        e = m-1

print(ans)

오랜만에 다시 풀었는데 기억이 안나 차근차근 풀었습니다.

좌표의 범위가 10억이고 집의 범위가 20만이므로 큰 숫자들로 보아 이진탐색의 가능성을 열어두었고 공유기간 거리를 매번 설정하고 이를 집 전체를 탐색하며 가능불가능 여부를 판단한다고 했을때 시간복잡도는 20만 × log(10억)입니다.

2^10=1024이므로 log_2(10억)은 30보다 작은 수이기에 전체시간복잡도는 600만 이어서 시간제한 2초(파이썬 기준 4000만)보다 작아 해도되겠다라는 판단이 섰습니다.

제일 이상적인 배치를 e에놓고 (첫번째는 무조건 설치하기 때문에 c-1로 나누어줍니다) 이진탐색을 하며 가장 마지막 성공을 정답으로 최신화 해줍니다. 

설치가능여부 확인은 맨앞에 먼저 설치했다고 가정하고(c-1), 집을 앞에서 부터 확인하며 이전 설치위치보다 m이상 거리가 있는곳에 설치를 반복하며 c개 전부 설치하면 1 전체를돌았는데도 설치를 하지 못했다면 0을 반환해 판단하였습니다.