[백준]2110번: 공유기 설치

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

2110번: 공유기 설치

---

처음 풀이

1. 가능한 모든 조합 nCc를 구한다

2. 가장 떨어진 두 공유기 사이의 거리를 구한다

from itertools import combinations

def minDist(arr):
  result=1e9
  for i in range(len(arr)-1):
    result = min(result,arr[i+1]-arr[i])
  return result
  
n, c = map(int,input().split())
houses=[]
for i in range(n):
  houses.append(int(input()))

houses.sort()

combi = list(combinations(houses,c))

result=0
for i in combi:
  result = max(minDist(i),result)

print(result)

결과: 메모리 초과

 

조합을 구해서 리스트에 저장하는 과정에서 메모리 초과가 난 듯.

n과 c가 최대 20만까지 될 수 있기 때문.

---

두 번째 풀이: binary search

 

두 공유기 사이의 거리는 1~10억이 될 수 있다. (문제조건: 집 좌표는 0부터 10억)

 

두 공유기 사이의 간격을 x로 하여, 공유기를 1번 집부터 마지막 집까지 차례대로 설치해본다.

최종적으로 설치되는 공유기의 수가 c개보다 많다면, 두 공유기 사이의 최대 간격은 x보다 커질 수 있다. --> x를 저장하고 x를 늘려준다.

최종적으로 설치되는 공유기의 수가 c개보다 적으면, 공유기 사이의 간격을 줄여야 공유기를 c개 설치할 수 있다. --> x를 줄여준다.

 

이렇게 x를 중간값부터 시작하여 조정해가면서 공유기 개수를 파악하면 된다.

이때, 집 좌표가 무작위로 입력되므로 x를 조정하는 작업을 하기 전에 집 좌표를 오름차순으로 정렬해주어야 한다.

 

import sys
input = sys.stdin.readline

n, c = map(int,input().split())
houses=[]
for i in range(n):
  houses.append(int(input()))

houses.sort() #집 좌표 정렬

start = 1
end = houses[-1]-houses[0]
answer = 0

while start <= end:
  mid = (start+end)//2
  cur = houses[0]
  cnt=1

  #1번 집부터 간격을 mid로 하여 공유기 설치해보기
  for i in range(1,n):
    if houses[i] >= cur+mid:
      cur=houses[i]
      cnt += 1
      
  #설치된 공유기 수가 c보다 많으면 간격을 저장하고 증가시키기
  if cnt >= c:
    start = mid+1
    answer=mid
  #설치된 공유기 수가 c보다 적으면 간격을 감소시키기
  else:
    end = mid-1

print(answer)

 

입력을 readline이 아니라 input으로 받으면 백준에서는 시간 초과가 나니까 조심