[백준] 2110번 : 공유기 설치

[백준] 2110번 : 공유기 설치

2110번: 공유기 설치

2110번: 공유기 설치

📄 문제개요

• 해당문제는 N개의 집이 수직선위에 있을때, 공유기 C개를 각 집에 설치하여, 최대한 많은곳에서 와이파이를 사용하고자 한다.
• C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

🤔 문제분석

• 집의 개수가 N (2 ≤ N ≤ 200,000) 이고 좌표는 Xi(0≤ Xi ≤ 1,000,000,000) 이기때문에 O(N^2)으로는 문제를 해결 할 수 없다. 해당문제를 해결하기 위하여 O(NlogN)의 방법으로 문제를 생각해보아야한다.
• logN의 알고리즘은 이분탐색으로 생각 해 볼 수 있다.
• 파라메트릭 서치 문제의 관점으로 풀어본다.
• 최적화 문제를 결정문제로 관점을 바꿔서 푸는 문제로, C개의 공유기를 놓았을때 최대의 거리값을 구해야한다.
  • 거리값을 넓히는경우 : 거리값이 넓어지면 공유기를 놓을 수 있는 수가 줄어든다.
  • 거리값을 좁히는경우 : 거리값이 좁아지면 공유기를 놓을 수 있는 수가 줄어든다.
• 그렇다면, 거리값을 기준으로 각각의 공유기를 놓을 수 있는 개수를 카운팅한다.
  • 개수가 많아진다면 거리값을 늘린다.
  • 개수가 적어진다면 거리값을 줄인다.
• 해당 문제안에서 개수가 C인 경우중에서 가장 큰 거리값을 찾으면 된다.

📝 의사코드

1. 거리값을 판별하기위해 초기 거리 값을 설정한다.
   1. 좌표값이 가장 큰 집 - 좌표값이 가장 작은집 = 공유기를 놓을 수 있는 최대 거리
   2. 공유기를 놓을 수 있는 최대거리 // 2 를 통하여 이분탐색을 실시한다.
2. 공유기를 놓을 수 있는 거리로 공유기를 놓을 수 있는 수를 카운팅한다.
3. 공유기를 놓을 수 있는 수가 C보다 크다면, 거리를 넓혀야 함으로, start = mid + 1 로 설정한다.
4. 공유기를 놓을 수 있는 수가 C보다 작거나 같다면, 거리를 좁혀야 함으로, end = mid - 1 로 설정한다.
   1. 여기서 최대거리값을 갱신하는데 공유기의 개수가 C인경우 최대값을 갱신해주면된다. 여기서 계속 최대값을 갱신하는 이유는 다음 end = mid - 1 서치일때는 무조건, 길이가 더 짧을 수 밖에 없다.
5. 이분탐색이 끝나면 최대거리값을 출력한다.

💻 코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())

home = []
for _ in range(N):
    home.append(int(input()))

home.sort()

start = 0
end = home[-1] + home[0] # 공유기를 놓을 수 있는 최대거리중 중간값
ans = 0
while start <= end:
    mid = (start + end) // 2

    prev = home[0]
    cnt = 1
    for i in range(1, len(home)):
        if home[i] - prev >= mid: # 공유기를 놓을 수 있다면
            prev = home[i]
            cnt += 1
            

    if cnt >= C:
        ans = max(mid, ans)
        start = mid + 1
    else:
        end = mid - 1
        
print(ans)

🎯 피드백 및 개선사항

• 처음에 이분탐색으로 문제를 접근했을때 어떤 것을 기준으로 문제를 해결할지 생각이 나지 않았습니다.
• 공유기 사이의 거리를 최대 라는 키워드로 접근하여 이분탐색 파라메트릭 서치를 적용하여 생각해보아야 합니다.

❓다른사람은 어떻게 풀었을까?

• 문제풀이 방법이 정해져있는 문제이다. 대부분의 문제들이 이분탐색으로 문제를 접근하여 풀이 하였습니다.