실1
확실히 실버 상위권으로 가니까 문제가 어려워진다.
문제는 구글에 풀이를 검색하면 상위에 올라와 있는 글들이 대체 문제를 풀고서 풀이를 올려놓은건지 아닌지도 모를만큼 형편없는 풀이와 코드를 올려놓았다는 것이다.
https://velog.io/@seanlion/boj2110
이 블로그에 글을 읽으니 이해가 바로 되었다. 내 풀이로 이해가 힘들다면 위에 블로그에 가보면 바로 이해가 가능할 것이다.
먼저 공유기 설치 문제는 이분탐색 문제인데, 최대로 설치할 수 있는 거리를 탐색하는 것이 문제 핵심이다.
더 문제를 쉽게 파악할 수 있는 키워드는 단위 거리 라는 단어이다.
이 단위 거리는 인접 공유기 간 거리의 최대값을 칭한다. 즉 내가 찾아야 하는 거리의 최대값, 답을 말한다.
예를 들어 문제의 테스트는 [1,2,8,4,9] 이다.
그렇다면 내가 탐색해야 할 단위거리 는 1 ~ 8(max - min) 사이의 거리일 것이다.
예를 들어 단위거리가 1이라고 해보자.
단위거리가 1이면 공유기는 1에 설치, 2에도 설치, 4에도 설치, 8에도 설치, 9에도 설치되어야 할 것이다.
단위거리가 2라면 공유기는 1에 설치, 2에는 설치되지 않아도 되고, 4에 설치되어야 하고, 8에 설치되어야 한다.
단위거리가 8이라면 1에 설치 9에 설치 나머지 설치 불가 이다.
단위거리가 7이라면 1에 설치 8에 설치 나머지 설치 불가 이다.
단위거리가 6이라면 1에 설치 8에 설치 나머지 설치 불가 이다.
이런식으로 이분탐색을 통해 안쪽으로 값을 좁혀 나간다.
C는 3이라고 주어졌으니, C보다 설치할 수 있는 공유기 개수가 작을 경우에는 단위거리를 줄여나가고 C보다 설치할 수 있는 공유기 개수가 클 경우에는 단위거리를 늘려나간다.
C와 설치할 공유기 개수가 같을 경우에는 거리의 최대값을 구하라 했으니, 단위거리를 1씩 늘리면서 계산한다.
공유기 개수를 산출하는 함수를 만드는게 꽤 중요하다.
# 거리를 탐색하는 것
# C 개 만큼 선택했을 때, 최소 거리
# n 개 중 C 개 선택했을 때,
n, c = map(int, input().split(" "))
houses = []
for i in range(n):
houses.append(int(input()))
def solution():
houses.sort()
start, end = 1, houses[-1] - houses[0]
# 단위 거리가 1 ~ 8 까지 있고, 단위 거리 대로 공유기를 설치했을 때 맞아떨어지는 개수가 공유기 개수일 경우
return binary_search(houses, start, end)
def binary_search(houses, start, end):
# 단위 거리를 이분 탐색
# 함수는 end값
mid = (start + end) // 2
count = find_house(mid, houses)
if start > end:
return mid
if count < c:
# 카운트가 C보다 적으면 단위거리가 너무 넓다는 뜻
return binary_search(houses, start, mid-1)
elif count >= c:
# 카운트가 c보다 크거나 같으면 단위거리가 너무 좁다는 뜻 = 단위거리를 넓혀야 한다. 최대값에 가까워져야 한다.
return binary_search(houses, mid+1, end)
#공유기 개수를 산출하는 함수
def find_house(gap, houses):
start = houses[0]
count = 1
for i in range(1, len(houses)):
# start에서 gap을 합친 것보다 크거나 같은 값을 만났을 때
# 그 곳에 공유기를 설치한다. 그리고 그 공유기를 설치한 장소를 start로 갱신
if start + gap <= houses[i]:
count += 1
start = houses[i]
return count
print(solution())