반응형
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

이분탐색 문제.
이분탐색 값의 기준은 '공유기 사이의 거리'이고,
공유기 사이의 거리를 토대로 주어진 문제 조건에 맞게 공유기 개수를 증가시키면서
이분탐색으로 최적의 '공유기 사이의 거리'를 구하는 문제.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
n, c = map(int, sys.stdin.readline().split()) | |
arr = [] | |
for _ in range(n): | |
arr.append(int(sys.stdin.readline())) | |
arr.sort() | |
start, end = 1, arr[-1] - arr[0] | |
result = 0 | |
while start <= end: | |
mid = (start + end) // 2 | |
idx, count = 0, 1 | |
for i in range(1, len(arr)): | |
# idx 위치에 공유기 설치했을 때 mid 거리 안에 i 위치의 집까지 전파가 닿지 않을 경우 | |
if arr[idx] + mid <= arr[i]: | |
# 공유기를 하나 추가한다. | |
count += 1 | |
# 다음 집의 위치에 공유기를 설치한다. | |
idx = i | |
# 공유기 개수가 c보다 작을 경우 | |
if count < c: | |
end = mid - 1 | |
# 공유기 개수가 c보다 클 경우 | |
elif count >= c: | |
result = mid | |
start = mid + 1 | |
print(result) | |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] 프로그래머스. 지형 이동 (Level 4) (0) | 2020.02.15 |
---|---|
[Python] 백준 13460. 구슬 탈출 2 (0) | 2020.02.14 |
[Python] 프로그래머스. 영어 끝말잇기 (Level 2) (0) | 2020.02.12 |
[Python] 백준 17281. ⚾ (2) | 2020.02.11 |
[Python] 백준 1021. 회전하는 큐 (0) | 2020.02.10 |