[BOJ] 2110번 공유기 설치 / 사용언어 : 파이썬(python)

※ 문제링크

2110번: 공유기 설치

※ 관련문제

[BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python)

해당문제는 이분탐색과 매개변수탐색을 활용하여 푸는 문제였다. 풀이방법을 찾기까지는 어려웠지만 실제로 구현하는 것은 그리 어렵지 않았다. 자세한 풀이방법과 코드는 아래와 같다.

1. 집의 좌표와 공유기의 갯수를 입력받아 값을 저장한다.

2. 공유기를 설치할 수 있는 최소거리를 0으로 최대거리를 집의 좌표차의 최댓값 + 1로 설정한다.

+ 최댓값에 +1을 한 이유 : 함수상 사용할 mid 값을 start값과 end값을 2로 나눈 몫으로 사용할 것이기 때문에

3. 거리별로 설치할 수 있는 공유기의 갯수와 그 최댓값을 구할 함수를 작성한다.

4. 결과값을 출력한다.

 

N, C = map(int, input().split())
locs = []
for _ in range(N):
    locs.append(int(input()))
locs.sort()
start = 0
end = locs[-1] - locs[0] + 1
# 입력값이 (2, 2) (1) (25)일때, 
# +1을 하지 않았을 경우 : 23 / +1을 했을 경우 : 24
value = -1
def check(locs, start, end, C, value):
    mid = (start + end) // 2
    cnt, cp = 1, 0
    i = cp + 1
    while cnt < C and i <= len(locs)-1: 
    # 공유기 설치가능여부 체크 및 확인
        if locs[i] - locs[cp] >= mid:
            cp = i
            i = cp+1
            cnt += 1
        else:
            i += 1
    if cnt < C:
    # 조건을 만족하지 못하면 거리를 줄여서 탐색할 수 있게 재귀함수
        end = mid
        return check(locs, start, end, C, value) 
    else:
    # 조건을 만족하면 탐색 종료 후 결과값 출력
        start = mid
        if value == mid:
            return value
        else:
            value = mid
            return check(locs, start, end, C, value)
print(check(locs, start, end, C, value))

 

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.