[백준 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억개) 완전탐색보단 정답을 한번에 효율적으로 찾을 수 있는 알고리즘을 생각하려고 했음

 

가장 크게 차이나는것을 C로 나눠서 해보기.. 등등 여러가지 해봤으나 한번에 찾을 수 있는 알고리즘은 없었음.

 

결국 다 탐색해야하는데 데이터가 1억개라서 시간초과 판정을 안받는 방법을 고려해야 했음.

 

 

 

 

해결 아이디어

---

공유기 사이의 GAP을 이진탐색으로 하나씩 뽑아서 확인해보면 된다.

 

데이터가 클 때 이진탐색을 한번 고려해보아야 하지만 이런식으로 이진탐색을 생각할 줄은 몰랐다.

 

이번 경험으로 하나 챙겨간다.

 

 

 

이진탐색은 흔히 start, end, mid 를 정하고 mid를 기준으로 왼쪽, 오른쪽중 한 곳으로 다시 탐색을 하는 식이다.

 

참고 : 2021/02/05 - [Algorithm/Binary Search] - 이진탐색 이론

이진탐색 이론

 

맨 처음 start, end 의 초기화는

start = 1

end = data[-1] - data[0] 이렇게 둔다.

 

어차피 숫자는 겹치는 집이 없다고 문제에서 주어졌기 때문에 가장 작은 gap 은 1이다. 그래서 start 를 1로 둔다

그리고 가장 큰 gap을 구해서 end로 초기화한다.

 

예시 데이터가 아래와 같이 주어졌다고 생각해보자.

5 3

1

2

4

8

9

start = 1

end = 8 (9 - 1)

이 된다.

 

[STEP 1]

데이터가 1억개 이므로 모든 gap를 다 확인해 볼 수 없으므로 이진탐색을 도입한다.

1 ~ 8 (start ~ end) 의 중간값인 4를 gap으로 두고 확인해본다.

gap = 4

 

gap = 4 일때 공유기는,

1 2 4 8 9

1과 8에 설치가 된다.

 

공유기는 3개가 설치되어야 하니까 gap을 줄여야 하는 상황이 된다.

 

여기서 이진탐색을 이용해 mid를 기준으로 왼쪽부분을 탐색하는 것이 gap을 줄이는 것이다.

 

[STEP 2]

end = gap - 1 으로 두고 다시 gap을 구해보자

1 ~ 3 (start ~ end)

gap = 2

 

gap = 2 일때 공유기는

1 2 4 8 9

1, 4, 8에 설치가 된다.

 

공유기는 3개가 설치되어야하는 상황에 맞다.

그러니 일단 gap = 2일때가 정답이 될 수 있다고 저장을 해두고

다시 gap을 늘려서 확인을 해보자

 

[STEP 3]

start = gap + 1 로 두고 다시 gap를 구해보자

3 ~ 3 (start ~ end)

gap = 3

 

gap = 3 일때 공유기는

1 2 4 8 9

1, 4, 8에 설치가 된다.

 

공유기는 3개가 설치되어야하는 상황에 맞다.

그러니 또 gap = 3일때가 정답이 될 수 있다고 저장을 해두고

다시 gap을 늘려서 확인을 해보자.

 

[STEP 4]

start = gap + 1

4 ~ 3 (start ~ end)

 

start > end 상황이 되었으니 이진탐색은 종료되고 현재 저장되어있는 gap = 3 이 정답이 된다.

 

 

 

 

정답코드

---

n, c = map(int, input().split())
data = []
for i in range(n):
    data.append(int(input()))
data.sort()
start = 1
end = data[-1] - data[0]

result = 0
while start <= end:
    gap = (start + end) // 2
    count = 1

    temp = data[0]+gap
    for i in range(1, n):
        if temp <= data[i]:
            count += 1
            temp = data[i] + gap

    if count >= c:
        start = gap + 1
        result = gap
    else:
        end = gap - 1

print(result)

 

 

 

실수했던 점

---

내가 문제 풀 때 실수했던 곳은 2개가 된다.

 

1. 이진탐색의 분기조건

 

처음에 설계를 했을 때

count < c : gap 감소

count == c : 현재 gap 저장, gap 증가

count > c : gap 증가

 

이렇게 설계를 했었다.

 

하지만 count > c 일때도 정답에 저장을 해주어야 했다.

왜냐면 실제 count 가 c 보다 크다고 해도 공유기는 c개 이니까 c개가 설치되었다고 볼 수 있다.

결국 중요한건 가장 인접한 두 공유기 사이의 거리 (gap) 이다.

 

정답 설계는

count >= c : 현재 gap 저장, gap 증가

count < c : gap 감소

이다.

 

 

2. 공유기 설치 시뮬레이션 temp 계산

 

처음 코드를 짰을 때 count 계산 코드는

 for i in range(1, n):
        if temp <= data[i]:
            count += 1
            temp += gap

이었다. 

temp = data[i] + gap 가 아닌

temp += gap 으로 했다.

 

이 두 방식의 차이는 크다.

temp += gap 으로 하면 집의 위치를 고려하지 않은 상태로 gap을 계산하게 된다.

실제 집끼리의 gap을 구하지 못하는 것이다.