백준 - 공유기 설치 Python

백준(BOJ) - 공유기 설치

문제풀이 : 이진 탐색, 파이썬

해결방법

공유기를 시작 위치에 먼저 설치해두고, 간격을 설정하면서 하나씩 설치해 나가는 문제이다.

이때 간격을 설치하는 방법으로 이진 탐색을 활용하면 된다.

최소 간격은 1(문제에서 한 집에는 공유기를 하나만 설치할 수 있다고 했으므로, 최소 간격은 1)

최대 간격은 [-1]인덱스와 [0]인덱스의 차이이다.

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

house.sort()
start = 1 #  최소 간격
end = house[-1] - house[0] # 최대 간격
result = 0

while start <= end:
    mid = (start + end) // 2 # 설치해나갈 간격
    temp = house[0]
    count = 1
    for i in range(1,n):
        if house[i] >= mid + temp:
            count += 1
            temp = house[i]
    
    if count >= c:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

실패한 방법

n개의 집중 c개를 설치하면 되므로 조합을 먼저 생각해서 풀었으나,

메모리 초과 오류를 받았다..

from itertools import combinations

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

house.sort()
combi = list(combinations(house, c))
result = -1e9
for arr in combi:
    min_sum = 1e9
    for i in range(1,len(arr)):
        min_sum = min(min_sum ,arr[i] - arr[i-1])
    result = max(result, min_sum)

print(result)