문제
풀이
-
백준의 기타 레슨과 유사
-
바킹독 님 블로그를 참고하면 이 문제는 파라메트릭 서치 = 매개 변수 탐색 문제로, 조건을 만족하는 최소/최대를 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법을 통해 풀 수 있다
-
최대/최소를 구하는 방식을 이분탐색을 통해서 그 범위를 좁혀나가면서 현재 구한 값이 조건에 맞는가? 맞다면/틀리다면 다음 조건은 어떻게 할지를 결정해나가면서 풀어가는 방식이다
-
일반 이분 탐색의 경우 은도끼 금도끼 문제였다면, 이 문제는 은색에 가깝냐, 금색에 가깝냐 정도로 해석하면 될 것 같다.
다른 사람 풀이 참고한 풀이
-
구하려는 것
- 가장 인접한 공유기 사이의 최대 거리
- 여기서 최대라고 해서 헷갈리면 안 되는데, 가장 인접한 공유기 사이의 거리이기 때문에 결국 해석하자면 최소 이 거리보다는 멀어야 설치할 수 있음 이 된다. 최소를 구하는 문제는 아니다. 조건을 만족하는 범위 내에서의 최대를 구하는 문제다.
- 이 말이 어려울 수 있는데, '최소 이 거리보다는 멀어야 설치할 수 있음'에서 '이 거리'를 만족하는 거리는 무수히 많을 수 있다. 3~10까지의 거리가 모두 공유기 3개를 설치하는 조건을 다 만족한다면 우리가 구하려는 값은 이 중에서 최대값인 10이 된다.
-
최소값, 최대값 = 공유기는 집에 설치할 수 있고, 집은 최소 한 칸씩 떨어져 있으므로 최소는 1칸, 최대는 가장 먼 집과 가장 가까운 집 사이의 거리가 된다.
-
이분탐색을 통해서 구한 공유기의 최소 설치 거리보다 더 멀거나 같다면 공유기를 설치하고 설치한 공유기의 개수를 추가해준다
-
만일 공유기의 개수가 C를 초과하게 된다면 너무 많은 공유기가 설치된 것으로, 이는 공유기의 설치 거리가 너무 가깝다는 것이다. 더 멀게 하기 위해서는 left의 값을 올려준다
-
하지만 만약 공유기의 설치가 끝났는데도 여전히 C보다 적다면 공유기의 설치 거리가 너무 멀었던 것이다. 더 가깝게 하기 위해서는 right의 값을 줄여준다.
-
하지만 만약에 정확하게 C만큼 설치되었다면? 우리는 지금 조건을 만족하는 값들 중에서의 최대값을 구하고 있다. 위에서 말했듯 정확하게 C만큼 설치된 거리가 3~10까지 있다면 우리가 구하려는 값은 10이다. 이분탐색을 통해 현재 6이라는 거리를 구했고 6일 때 C만큼 설치되었다면? 이보다 더 큰 값도 C를 만족할 수 있는지를 구해야 한다. 즉 left를 올려준다
-
하지만 만약 7만큼 거리를 설정했더니 갑자기 C보다 더 적은 숫자의 공유기가 설치된다면 구하려는 최대는 6인게 된다. 이분탐색을 통해서 6보다 큰 숫자들 중에서 C만큼 설치될 수 있는 거리를 찾다가 찾지 못한다면 결국 계속 right의 숫자가 줄어들게 되고, 반복문의 종료조건인 left>right를 만족하는, left = 7, right = 6인 결과가 나오게 되고, 우리는 right를 출력하면 정답을 찾을 수 있다.
-
left = 7인 상태에서 right와 mid의 값만 변경되면서 계속 내려온다고 생각하면 된다
N, C = map(int, input().split())
house = [int(input()) for _ in range(N)]
house.sort()
def sol():
left, right = 1, house[-1]-house[0]
while left<=right:
mid = (left+right)//2
now, c = house[0], 1
for next in house[1:]:
if next>=now+mid:
c += 1
if c >= C:
break
now = next
if c >= C:
left = mid+1
else:
right = mid-1
print(right)후기
- 솔직히 이분탐색은 코테에서 나오면 한 번도 제대로 푼 적이 없음..ㅠㅠ
