Chap 15. 이진탐색 - Q29. 공유기 설치

1. 공유기 설치

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😊 2차 시도 (성공)

n, c = list(map(int, input().split()))
array = []

for i in range(n):
    array.append(int(input()))

array.sort()

start = 1
end = array[-1] - array[0]

answer = 0

while start <= end:
    mid = (start + end) // 2
    house = array[0]
    count = 1

    for i in range(1, n):
        if array[i] >= house + mid:
            count += 1
            house = array[i]

    if count < c:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid

print(answer)


b. 🙄 회고

내 풀이

  • 공유기 c개를 사용하여 만들 수 있는 최대 공유기 영역을 구하면 된다.
  • 이런 문제는, 문제에서 제시된 것과 이진 탐색에 사용할 길이를 따로 생각해야 한다.

반성

  • 문제 이해가 잘 안됬었다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 책 답안

python-for-coding-test/3.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] 2110번: 공유기 설치 (acmicpc.net). Baekjoon. (accessed Oct 15, 2021)

이 글이 도움이 되었나요?

신고하기
0분 전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.