백준(BOJ) 2110 공유기 설치(Python)

문제 내용

 

이분 탐색 문제.

공유기 간의 거리를 이분 탐색의 변수로 두고, 모든 집을 탐색하며 현재 거리로 두 집 간에 공유기를 설치할 수 있는 지를 확인한다.

공유기를 설치할 수 있다면 공유기 개수를 늘린다.

탐색이 끝나고 설치할 수 있는 공유기 개수가 입력받은 공유기 개수 이상이라면 ans를 갱신하고 start를 변경한다.

그렇지 않다면 end를 변경한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
L=[]
for i in range(n):
    L.append(int(input()))
L.sort()
s=1
e=L[n-1]-L[0]
ans=0
while s<=e:
    mid=(s+e)//2
    c=1
    p=0
    for i in range(1,n):
        if L[i]>=L[p]+mid:
            c+=1
            p=i
    if c<m:
        e=mid-1
    else:
        s=mid+1
        ans=mid
print(ans)

 

python으로 제출하면 시간 초과가 터져서 pypy로 제출해 통과했다.

2019 부산과학고 정보 경시대회에 이 문제가 나왔는데, 그 때는 이걸 풀지 못 했던 기억이 있다.

신촌캠프 문제로 다시 만나게 될 줄은 몰랐는데...