문제
링크: https://www.acmicpc.net/problem/2110
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 83393 | 30466 | 21045 | 37.025% |
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1 복사
5 3
1
2
8
4
9
예제 출력 1 복사
3
힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
출처
Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO February 2005 Contest > Gold 3번
알고리즘 분류
풀이
이진 탐색을 써서 풀어야 한 단다.
이진 탐색을 쓸 생각을 전혀 못했다.
생각을 돌려서 거리를 기준으로 탐색하는 방법이 효율적인것 같음
일단
- 집
n개가 주어진다. c개의 공유기를 설치하되, 공유기 간 최소 거리를 최대로 설정해야 한다.- 입력된 집 위치는 정렬되지 않은 상태로 주어질 수 있다.
그러니 집 거리를 우선 정렬시켰다
n, c = map(int, input().split())
houses = sorted(int(input()) for _ in range(n)) # 집 위치 정렬이진 탐색으로 공유기 간 가능한 최소 거리를 탐색해야 한다.
최소거리를 1로 잡고 가장 먼 거리를 최대 거리로 잡는다
min, max = 1, houses[-1] - houses[0] #최대 최소 거리특정 거리로 공유기 c개가 설치 가능한지 확인한다.
def install(dis):
cnt = 1
cur = houses[0]
for i in range(1, n):
if houses[i] - cur >= dis:
cnt += 1
cur = houses[i]
if cnt >= c:
return 1
return 0이진탐색으로 가능한 최고 거리의 최대값을 찾아낸다.
while min <= max:
mid = (min + max) // 2
if install(mid):
result = mid
min = mid + 1
else:
max = mid - 1정답
n, c = map(int, input().split())
houses = sorted(int(input()) for _ in range(n)) # 집 위치 정렬
min, max = 1, houses[-1] - houses[0] #최대 최소 거리
result = 0
def install(dis):
cnt = 1
cur = houses[0]
for i in range(1, n):
if houses[i] - cur >= dis:
cnt += 1
cur = houses[i]
if cnt >= c:
return 1
return 0
while min <= max:
mid = (min + max) // 2
if install(mid):
result = mid
min = mid + 1
else:
max = mid - 1
print(result)
(백)이진 탐색
