2110번: 공유기 설치 / gold 4 / 이분탐색

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

2110번: 공유기 설치

 

 

메모리 초과

'''
2110번: 공유기 설치 / gold 4 
'''
import sys
import itertools

input = sys.stdin.readline

n, c = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()
comb = list(itertools.combinations(arr, c))
max_res = 0
for i in range(len(comb)):
    min_res = int(1e9)
    for j in range(1, c):
        tmp_res = comb[i][j] - comb[i][j - 1]
        if min_res > tmp_res:
            min_res = tmp_res
    if min_res > max_res:
        max_res = min_res
print(max_res)

오답 코드 (구현 생각)
- n개 중 c개 선택 한 경우의 수에서 -> 공유기 사이의 최대 거리 인놈 찾기
- 시간 초과가 날 것 같은 기분?
1. arr 리스트 만들어서 입력 받은 것 오름차순 정렬하기
2. comb 조합 경우의 수 만들기
3. 경우의 수 하나하나 모두 확인하기

---

정답

'''
2110번: 공유기 설치 / gold 4 / 이분탐색
'''
import sys

input = sys.stdin.readline

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

max_res = 0
start = 1
end = arr[-1] - arr[0]

while start <= end:
    mid = (start + end) // 2
    now = arr[0]
    count = 1
    for i in range(1, len(arr)):
        if arr[i] >= now + mid:
            count += 1
            now = arr[i]
    if count >= c:
        start = mid + 1
        max_res = mid
    else:
        end = mid - 1
print(max_res)

 

이분탐색 활용

- 최소거리(1) 와, 최대거리(arr[-1]-arr[0])를 start, end로 지정하여 이분 탐색 진행하기

- mid 는 각 공유기의 간격을 의미

- mid 간격에 따라서 집들의 개수가 얼마나 count 되었는지 확인 하기

(count 가 c보다 크거나 같을 때, mid 간격이 좁다는 의미)

(count 가 c보다 작을 때, mid 간격이 크다는 의미)

 

 

해당 문제가 어려운 점

1. mid 를 간격으로 해서 집들의 개수를 count 하려는 아이디어를 전혀 생각하지 못함.

두 공유기 사이의 최대 거리 == 최대 중간값 (mid의 최댓값)