[백준] 2110번 : 공유기 설치 (파이썬, pypy)

문제

나의 첫번째 답안

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

for i in range(n):
    x.append(int(input()))
x.sort()
mn,mx=(x[1]-x[0]),(x[-1]-x[0]) ###############
result=0
while mn<=mx:
    cnt=1
    mid=(mn+mx)//2 
    v=x[0] 
    
    for i in range(1,len(x)):
        if x[i]>=mid+v:
            v=x[i]
            cnt+=1
            
    if cnt>=c:
        result=mid 
        mn=mid+1
    else:
        mx=mid-1
print(result)

최소 간격(mn)을 배열의 첫번째 값과 두번째 값의 차이로 하면 실제 최소 간격이 이와 다를 수 있으므로 옳지 않다. 따라서 최소 간격을 1로 설정해주고 순차적으로 늘려주어야 한다.

나의 최종 답안

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

for i in range(n):
    x.append(int(input()))
x.sort()
mn,mx=1,(x[-1]-x[0])#최소 간격, 최대간격 계산
result=0
while mn<=mx:
    cnt=1 #공유기의 개수, 기준위치를 만족하는 집의 개수
    mid=(mn+mx)//2 #설치 간격(기준 위치)
    v=x[0] #처음집부터 순차적으로 설치
    
    for i in range(1,len(x)):#배열 접근, 인덱스0은 제외
        if x[i]>=mid+v: #현재 집의 위치값(배열값)이 간격보다 크다면
            cnt+=1 #공유기의 개수 1증가
            v=x[i]  #값을 현재 값으로 갱신
            
    if cnt>=c: #적게 설치되어야 함, 간격을 늘려야 함
        result=mid #인접한 공유기 간 최대 거리
        mn=mid+1
    else:#더 설치되어야 함, 간격을 줄여야 함
        mx=mid-1
print(result)#거리 출력

접근 방법

• 이진 탐색 문제이다.
• 특정 간격을 기준으로 중간간격을 계산하여 공유기를 설치해야 한다.
• 공유기가 더 필요하면 중간간격을 줄이고, 공유기를 보다 적게 설치할 필요가 있으면 간격을 늘린다.
• 이를 최소간격과(mn) 최대간격(mx)가 같아질 때까지 반복한다.
• 최대간격을(mx) 계산해주기 위해 배열을 정렬해줄 필요가 있다.
• 최대가 되는 중간값(mid)을 찾는 것이 이 문제의 핵심이다.