[이코테] CH07 이진 탐색 실전문제 29번 공유기 설치

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

문제

2110번: 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1 복사

5 3
1
2
8
4
9

예제 출력 1 복사

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

처음 접근은 혹시 몰라 수학적으로 접근했는데

역시나 시간 초과....

이분탐색으로 풀라는 것 같은데

도저히 어떻게 해야할지를 모르겠었다

start,end 설정까진 하고

뭘 기준으로 잡아야 하나 싶었는데..

공유기 개수를 딱 C개! 가 아니라

이 C개가 되도록 거리를 조절해주면서 값을 찾아나가는 방법을 사용하는 것이었다

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
from bisect import bisect_left,bisect_right

N,C = map(int,sys.stdin.readline().split())
array = []
for _ in range(N):
    array.append(int(sys.stdin.readline().rstrip()))
array.sort()
end = array[-1] - array[0] # 최대거리
start = 1 # 최소거리
while start <= end:
    count = 1
    mid = (start + end) // 2
    current = array[0]
    for i in range(1,len(array)):
        if array[i] - current >= mid: # 만약 mid보다 떨어진 거리가 크다면 설치할 수 있는것.
            count +=1
            current = array[i]
    if count >= C: # 공유기가 더 설치되거나 딱 맞게 설치되는 경우, 범위를 넓혀야 한다 
        start = mid + 1 # 범위를 넓혀야 하는 거니까 mid를 더 넓혀야 적게 설치
        answer = mid
    else: # 공유기가 덜 설치된 경우, 범위를 좁혀야 한다
        end = mid - 1 # end를 줄이는 방법으로 mid를 더 좁혀야 많이 설치
print(answer)

 

아직도 너무 부족한 것 같다

이번달 안에 이코테 1회독 후 2회독도 들어가고

백준 프로그래머스 

열심히 풀어야겠다

아래는 .. 힌트만 보고 열심히 풀어본 코드