«   2022/08   »
  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 29 30 31      
Archives
Today
11
Total
93,048
관리 메뉴

차근차근

[백준 2110] 공유기 설치 본문

대학교/Algorithm

[백준 2110] 공유기 설치

SWKo 2020. 9. 4. 23:37

0. 제목

  • 백준 2110 공유기 설치
  • BOJ 2110 공유기 설치
  • Python 2110 공유기 설치

1. 문제

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

 

2110번: 공유기 설치

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

www.acmicpc.net

 


2. 풀이

  • 이진탐색을 사용하는 문제이다.
  • 두 공유기 사이 거리의 최대값과 최소값을 가장 먼저 구하고 중간값을 구해가며 정답을 구한다.
  • 중간값을 구할 때마다 설치 가능한 공유기 개수를 구한다.
  • 설치 가능한 공유기 개수와 입력받은 공유기 개수를 비교해가며 범위를 조정한다.
  • while문을 빠져나온 후 정답을 출력한다.

3. 코드

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(' '))
 
arr = []
for _ in range(n):
    arr.append(int(input()))
    
arr = sorted(arr)
 
low = arr[1- arr[0]
high = arr[-1- arr[0]
result = 0 # 결과값(최대 Gap)
 
while(low <= high):
    mid = (low + high) // 2 # mid는 gap
    
    value = arr[0]
    count = 1 # 설치중인 공유기 개수
    for i in range(1len(arr)):
        if arr[i] >= value + mid:
            value = arr[i]
            count += 1
    if count >= c: # c개 이상의 공유기를 설치할 수 있는 경우
        low = mid + 1
        result = mid
    else# c개 이상의 공유기를 설치할 수 없는 경우
        high = mid - 1
        
print(result)

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1697] 숨바꼭질  (0) 2020.09.06
[백준 1260] DFS와 BFS  (0) 2020.09.05
[백준 2110] 공유기 설치  (0) 2020.09.04
[백준 1874] 스택 수열  (0) 2020.09.03
[백준 1302] 베스트 셀러  (0) 2020.09.02
[백준 1236] 성 지키기  (0) 2020.09.02
0 Comments
댓글쓰기 폼