섹션4: 이분탐색(결정알고리즘)

이분탐색 푸는 유형: 답이 특정 범위 안에 알고 있을 때, 범위 좁히면서 찾는다.

 

2번: 랜선자르기

n개의 랜선 길이가 k개의 랜선 길이를 넘지 않는 것이 확실. -> 1 ~ 1000

중간값인 500이 답이 되는지 확인 -> 500은 답이 아님. 그럼 500보다 작은 쪽으로 감. -> 1 ~ 499

중간값인 250이 답이 되는지 확인 -> 11개 이상인데 8개밖에 나오지 않아서 답이 아님. -> 1 ~ 249

중간값인 125가 답이 되는지 확인 -> 18개가 나와서 답이 가능. -> 125이하는 답이 다 되므로 126 ~ 249에서 답이 있는지 확인.

... 이런식으로 이분검색이 끝날 때까지 한다.

lt = 1
rt = largest
while lt <= rt:
    mid = (lt + rt) // 2 # 한 개의 랜선 길이 (답)
    if Count(mid) >= n: # 답이 되는 경우
        res = mid
        lt = mid + 1 # 더 좋은 답을 찾아서 나아가기
    else: # 개수가 부족하여 답이 되지 않는 경우
        rt = mid - 1 # 긴쪽 버리기

 

3번: 뮤직비디오

비디오의 용량은 어떤 노래들보다 용량이 많다는 하에 진행이 됨을 기억하자.

 

4번: 마구간 정하기

lt, rt 범위를 두 말의 최대 거리로 두기.

lt 최소: 1.  rt 최대: 9. mid = (9+1)//2 = 5

첫번째 마구간 좌표에는 무조건 말을 넣기.

두번째 마구간 좌표하고의 거리를 구하기. (2-1) < 5 -> 배치 못함.

세번째 마구간 좌표하고의 거리를 구하기. (4-1) < 5 -> 배치 못함.

네번째 마구간 좌표하고의 거리를 구하기. (8-1) >= 5 -> 배치 함. +마지막 좌표: 8

다섯번째 마구간 좌표하고의 거리를 구하기. (9-8) < 5 -> 배치 못함.

5보다 긴것은 더 배치를 못해서 답이 안되니깐 rt=5-1로 바꾸기.

...이런식

만약 세마리 배치할수 있는데 네마리도 배치할수 있으면 답이 된다.

 

'거리 차'로 해야지 Time Error가 나지 않는다.