백준 문제풀이 - 2110 번
1. 요약 및 풀이방법
N개의 집에 C개의 공유기를 최대한 공평한 간격으로 설치하는 문제입니다.
이 문제는 처음 문제를 이해 하는 과정부터 많이 헷갈렸습니다.
가장 인접한 공유기의 사이의 거리를 최대로 하라는 요구의 결론은,
결국 공유기 사이의 거리가 최대한 공평하게 설치될 수 있도록 하는 것 입니다.
그다음 이 문제를 어떻게 이분탐색으로 풀이하느냐가 중요합니다.
공유기 사이의 간격이 될 수 있는 범위를 전체 범위로 두고,
이 전체 범위의 mid 값을 기준으로 이분탐색을 진행합니다.
이때, mid 값의 의미는 공유기 사이의 거리를 의미합니다.
따라서 mid 값의 거리만큼 공유기를 설치한 후,
- 설치한 공유기의 갯수가 C보다 작으면 공유기를 더 설치해야 하기 때문에, 공유기 사이의 간격을 줄여야합니다.
- 반대로 공유기의 갯수가 C보다 크면 공유기를 충분히 설치할 수 있기 때문에, 더 넓은 간격으로 설치합니다.
위의 두 경우가 이해가 안간다면, 다음의 예시를 들어보겠습니다.
종이에 하나의 선을 긋고, 그 선을 연필을 이용해 5등분을 해 봅니다.
(5등분을 하기 위해서는 선 4개를 같은 간격으로 그려야 합니다.)
선을 3개쯤 그렸을 때, 남은 간격을 보면 내가 선을 잘 그렸는지 못그렸는지 알 수 있습니다.
잘 못그렸다면 지우개로 지우고 이전에 그린 선의 흔적을 이용해 간격을 조절할 수 있습니다.
이때 너무 넓게 그렸었다면 조금더 좁게 그려야하고
너무 좁게 그렸었다면 조금더 넓게 그려야 합니다.
2. Code
import sys
def main():
N, C = map(int , input().split())
house = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
house.sort()
start = 1
end = house[-1] - house[0]
while start <= end:
mid = (start + end) // 2
count = 1
nearest = house[0]
for idx in range(N):
if house[idx] >= nearest + mid:
nearest = house[idx]
count += 1
if count < C:
end = mid - 1
else:
start = mid + 1
print(end)
if __name__ == "__main__":
main()3. 학습 내용
이 문제에서는 문제를 풀이하기 쉽도록 이해하는 과정이 제일 어려웠습니다.
또한 start 값을 초기화 하는 과정에서 기존에는 house[1] - house[0] 값으로 초기화 하였는데,
이 경우 처음 집과 두번째 집 사이의 거리가 먼 경우, start 값이 너무 빠르게 end로 수렴해버리는 문제가 있었습니다.
이에 대한 반례는 다음과 같습니다.
5 3
1
7
8
9
10
ans = 3
output = 0따라서 위와 같이 start=1로 초기화 하여 문제를 해결했습니다.
4. 결과
