백준/ Gold 5 문제 , 백준 파이썬 2110 , 공유기 설치

백준/ Gold 5 문제 , 백준 파이썬 2110 , 공유기 설치

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
오늘 푼 이진 탐색 문제들 중에선 제일 어려운 편인듯

 

<문제 출처>

 

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

2110번: 공유기 설치

------------------------------------------------------------------------------------------------------------------------------

 

 

우선 이전 이진 탐색 문제들 처럼 양 쪽을 설정해 줘야한다.

 

이때 집의 좌표가 랜덤으로 나오므로 sort() 를 사용해서 크기 순으로 정렬해준 뒤

 

 

 

close, far = 1, wifi[-1]

양 끝값을 설정해 준다.

 

이때 close 값을 wifi[0] 으로 설정해주면 틀리니 1로 설정해주고 끝값만 wifi[-1]로 설정한다.

 

 

(이전 문제들 low, high = 1, max(리스트) 로 설정하는 것과 같다.)

 

 

 

 

이후

 

while close <= far:

 

while 문 조건을 설정해주고

 

절반값을 구하기 전에

 

tmp=wifi[0]

 

변수에다가 맨 왼쪽값을 저장해준다. 이 값은 밑의 for문에서

 

 

for i in range(N):
        if wifi[i]>=tmp+divide:
            tmp=wifi[i]
            cnt+=1

 

갯수 체크를 하면서 값을 올려나갈 때 사용된다.

 

 

 

tmp=wifi[0] 다음에 

cnt=1

이 코드를 선언해 주었는데,

 

 

close 값을 올려나가면서 변경된 close 부터 cnt를 세어 나갈텐데 wifi[0] 값 자체의 위치도 포함해야하므로 cnt=1 부터 바로 시작하는 것이다.

 

 

for 문 다음엔

 

if cnt >= C:
        close=divide+1
        result=divide
    else:
        far=divide-1

으로 cnt 값에 따라 close 를 조정할 것인지 far을 조정할 것인지를 결정한다.

 

 

 

 

 

 

문제의 예시가 몇번의 루프를 돌며 값이 변하는지 체크하기위해 임의로 close와 far , cnt값을 루프를 돌때마다 확인해보았다.

 

1 4 2
3 4 3
4 4 3
4 3 2

 

그랬더니 위처럼 출력되는데, cnt 에 맞게 close와 far 값이 조정됨을 알 수 있다.

 

두번째 줄 처럼 cnt가 3 이 나왔지만 close는 3으로 없는 좌표이므로 다시 루프를 돌려주는 것도 확인할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

import sys 
input=sys.stdin.readline

N,C=map(int,input().split())
wifi=[]
for i in range(N):
    wifi.append(int(input()))
wifi.sort()
close, far = 1, max(wifi)
result=0

while close <= far:
    tmp=wifi[0]
    divide=(close+far)//2
    cnt=1
    for i in range(N):
        if wifi[i]>=tmp+divide:
            tmp=wifi[i]
            cnt+=1
    if cnt >= C:
        close=divide+1
        result=divide
    else:
        far=divide-1

print(result)