https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 이진 탐색으로 해결할 수 있는 문제였습니다. 그러나 일반적인 이진 탐색을 이용한 방법의 경우 start, end를 이용하여 mid값을 잡아주고 찾아야 하는 target이 있는 반면 이 문제는 target이라는 것이 딱히 없습니다.
따라서 target을 설정하는 것이 아닌 이진 탐색의 방법을 응용해야 한다는 것입니다.
문제 해결의 과정은 다음과 같습니다.
1. 집과 집 사이의 거리의 최솟값을 start로 최댓값을 end로 지정한다.
(문제에서 집 여러 개가 같은 좌표를 가지는 일은 없기 때문에 공유기 사이의 거리의 최솟값은 1, 최댓값은 입력받은 집들의 좌표를 정렬한 후 맨 마지막 원소와 맨 처음 원소 사이의 거리)
2. start와 end를 이용해 mid값을 구하고 해당 mid값을 공유기들 사이의 거리의 최솟값으로 정하였을때 C개만큼 설치할 수 있는지 확인한다.
3-1. C개만큼 설치할 수 없을 때는 공유기 사이의 거리가 큼. 따라서 end를 mid - 1로 설정하여 2번 과정 반복
3-2. C개만큼 설치할 수 있을 때는 공유기 사이의 거리를 하나씩 증가하여 최댓값을 찾음. 따라서 start를 mid + 1로 설정하여 2번 과정 반복
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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] # 공유기 사이 거리 최댓값
ans = []
while start <= end:
prev = data[0]
mid = (start + end) // 2
count = 1
for i in range(1, N):
if prev + mid <= data[i]:
prev = data[i]
count += 1
if count >= C:
start = mid + 1
ans.append(mid)
else:
end = mid - 1
print(max(ans))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14501: 퇴사 (Python) (1) | 2020.12.19 |
|---|---|
| 백준 알고리즘 1932: 정수 삼각(Python) (0) | 2020.12.18 |
| 백준 알고리즘 18310: 안테나(Python) (2) | 2020.12.10 |
| 백준 알고리즘 16234: 국영수(Python) (0) | 2020.12.09 |
| 백준 알고리즘 16234: 인구이동(Python) (0) | 2020.12.07 |