[백준] 2110 공유기 설치

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

문제에서 주어지는 공유기의 개수를 만족시키며 공유기간의 사이 거리를 구해야 하므로 이분 탐색을 이용하였습니다.

2) 알고리즘

• 이분탐색

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N, C = map(int, sys.stdin.readline().split())                   # 집의 개수, 공유기의 개수
home = sorted([int(sys.stdin.readline()) for _ in range(N)])    # 집의 위치
answer = 0

l, r = 1, home[-1] - home[0]            # 공유기간의 거리 최솟값과 최댓값
while l <= r:
    gap = (l+r) // 2                    # 공유기간 거리 중간부터 해서 탐색
    pre = home[0]                       # 처음 공유기를 설치하는 집을 기준으로 최초 선택
    cnt = 1                             # 공유기 설치한 집의 개수

    for i in range(1, N):
        if home[i] - pre >= gap:        # 이전에 설치한 집과 현재 집의 거리가 기준 보다 멀다면
            cnt += 1                    # 집의 개수 증가
            pre = home[i]               # 이전 집 변수에 현재 집 위치 넣기
        
        if cnt >= C:                    # 공유기 개수가 조건의 개수 이상이라면
            l = gap + 1                 # 거리를 늘려서 공유기 개수를 줄이기 위함
            answer = gap                # 정답에 현재 거리를 저장
            break
    else:               
        r = gap - 1         # 공유기 개수가 부족하다면, 거리를 줄이기

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

문제에서 공유기간의 거리를 수할때 이분 탐색을 떠올리는데 어려움이 있었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다