백준 2110 공유기 설치

백준 2110 공유기 설치

 

이분탐색!

 

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

2110번: 공유기 설치

 

최종적으로 원하는 값이 공유기 설치 간격!

mid값이 공유기 설치 간격이 나오도록 코드를 구성하는것이 좋을듯하다.

 

첫번째 집에는 무조건 공유기를 설치해야 한다.

---

 

아래 코드는 답안 코드를 보며 분석! accepted한 나의 코드다.

안보고 짤 수 있을 때까지 반복해서 풀 예정...

 

📄 나의 코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
house = list(int(input()) for _ in range(N))

# N, C = 5, 3
# house = [1,2,8,4,9]
house.sort() # [1, 2, 4, 8, 9]

left = 1 # 최소 간격
right = house[N-1] - house[0] # 최대 간격
result = 0 # 최종 결과값

while(left <= right):
    mid = (left + right) // 2
    cur = house[0] # 첫번째 집에 공유기 설치
    cnt = 1 # 첫번째 집에 공유기 설치

    for i in range(1, N): # 다음으로 공유기 설치할 집 탐방
        if house[i] - cur >= mid:
            cur = house[i] # i번째 집에 공유기 설치
            cnt += 1 # 공유기 설치 횟수 카운트

    # 범위 조정
    if cnt < C:
        right = mid - 1
    else:
        left = mid + 1
        result = mid

print(result)

 

---

디버깅하면 코드를 따라가면, 

N, C = 5, 3
house = [1,2,8,4,9]

이 조건인 경우, (1,0)집에 공유기 설치 mid=4

(8,0)에 공유기 설치 mid=2

(4,0)에 공유기 설치 mid=3

하고 결과값이 출력된다.