문제
https://www.acmicpc.net/problem/2110
접근
- 주어진 집들(n개)에 공유기(c개)를 설치할 때, 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제
- 가장 처음 든 생각은 집들 중 공유기를 설치할 집들을 선택하는 방법으로 접근하려 했으나, 이 방법의 시간 복잡도는 nCc이며, n과 c의 범위가 2 ≤ n ≤ 200,000, 2 ≤ c ≤ n 이므로 시간초과가 날 것 (제한시간 2초)
- 다른 방법 필요...!
- 우선 답이 될 수 있는 공유기 사이의 최대값은 이미 정해져 있고, 그 안에서 문제의 조건을 만족시키는 경우를 구하면 되기 때문에 이분탐색으로 접근
- 이분탐색의 경우 시간 복잡도는 O(n)
풀이
- lt와 rt는 각각 0, 집의 최대값 - 집의 최소값으로 초기화
- mid 값을 만족시키면서 공유기를 설치하려면 최소 몇개의 공유기가 필요한지 구하는 count 함수 작성
- 필요한 공유기의 수가 주어진 c보다 크거나 같을 경우, ans를 갱신하고 lt를 mid+1로 설정
- 필요한 공유기의 수가 주어진 c보다 작을 경우, mid 값이 작아져야 하므로 rt를 mid-1로 설정
import sys
input = sys.stdin.readline
def count(mid):
cnt = 1
now = house[0]
for i in range(n - 1):
if house[i + 1] - now >= mid:
cnt += 1
now = house[i + 1]
return cnt
n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]
house.sort()
lt = 1
rt = house[-1] - house[0]
ans = 0
while lt <= rt:
mid = (lt + rt) // 2
if count(mid) >= c:
ans = mid
lt = mid + 1
else:
rt = mid - 1
print(ans)
결과
'Python > Coding Test' 카테고리의 다른 글
1781 컵라면 (0) | 2022.02.10 |
---|---|
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |
11411 합 구하기 (0) | 2022.02.09 |
13702 이상한 술집 (0) | 2022.02.08 |