[백준]2110 공유기 설치(Python)

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

2110번: 공유기 설치

 

문제 접근 

 

<처음 접근 방식>

1. 입력한 집의 좌표를 정렬

2. C개를 선택할 수 있는 경우에서 가장 인접한 값(min)을 gap_list에 계속 추가

3. 그 중 최댓값 출력

 

<이분 탐색 아이디어>

1. 예제의 mid = 4, 공유기를 설치할 수 있는 곳은 마지막으로 설치한 곳과 설치예정 장소의 거리가 mid보다 커야함

2. 시작점에는 무조건 설치

    1~2  1 (x)

    1~4  3 (x)

    1~8  7 (o)

    8~9  1 (x)

    => C=2에 어긋 

 

<공유기 설치 위치의 조건>

1. 중간값보다 커야 설치 가능 => 이 때 중간값은 최소 거리와 최대 거리의 중앙을 의미!!

2. 다 설치를 했는데 C보다 작으면 공유기 간격 좁히기

3. 공유기 개수가 C보다 크면 공유기 간격 넓히기 

 

ex)

[1, 2, 4, 8, 9] 

start = 1, end = 8, cnt = 1, cur = 현재 집의 위치 = Houses[0]

 

mid = 4,

2-1 < 4 이므로 두 번째 집 공유기 설치x => cnt=1

4-1 < 4 이므로 세 번째 집 공유기 설치x => cnt=1

8-1 >= 4 이므로 네 번째 집 공유기 설치o => cnt=2

설치해야 하는 공유기 개수 3보다 작으므로 end를 mid-1로 설정하여 공유기 간격을 감소

 

mid = (1+3)//2 = 2,

2-1 < 2 이므로 두 번째 집 공유기 설치x => cnt=1

4-1 >= 2 이므로 세 번째 집 공유기 설치o => cnt=2

... 4번째 집o 5 번째 집 공유기 설치o => cnt=4

 

answer = 2, start = 3 ...

 

코드

 

처음 접근 방식 => 시간 초과 발생 

import sys
input = sys.stdin.readline

from itertools import combinations

N, C = map(int, input().split())

Houses = []

for _ in range(N):
    House = Houses.append(int(input()))

Houses.sort()
gap_list = []

for j in (combinations(Houses, C)):
    compo = list(j)
    max_gap = abs(compo[1]-compo[0])
    for k in range(2, C):
        max_gap = min(max_gap, abs(compo[k]-compo[k-1]))
    gap_list.append(max_gap)

print(max(gap_list))

 

이분탐색코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())

Houses = []

for _ in range(N):
    Houses.append(int(input()))

Houses.sort()

start, end = 1, (Houses[-1]-Houses[0])  # 최소 거리와 최대 거리(가장 멀리 떨어진 집)

answer = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 1
    cur = Houses[0] # 현재 집의 위치

    # 두번째 집부터 탐색
    for i in range(1, N):
        if Houses[i] - cur >= mid:    # 설치예정인 집이 마지막으로 설치한 곳과의 거리보다 크면 설치
            cnt += 1
            cur = Houses[i] # 마지막 설치위치 기록

    # 만약 총 설치개수가 C보다 크면
    if cnt >= C:
        answer = mid # 일단 기록 
        start = mid + 1 # 간격을 늘림
    else:   # C보다 작으면
        end = mid - 1 # 간격을 줄임 

print(answer)

 

문제 회고

 

마지막에 answer = mid를 하는 이유는 공유기 간의 거리를 늘려서 다시 탐색할 때, 목표수 이상 설치할 수 없는 경우가 발생할 수 있기 때문에 마지막 mid 값을 기억하기 위해서이다. 

 

 

참고

https://kill-xxx.tistory.com/entry/Python-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EA%B8%B0%EC%B4%88-%EB%B0%B1%EC%A4%80-2110%EB%B2%88-%EA%B3%B5%EC%9C%A0%EA%B8%B0-%EC%84%A4%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%92%80%EC%9D%B4

[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이