섹션 4. 이분 탐색(결정알고리즘) - 마구간 정하기

-

9월 6일 기준 두번째 푸는데 이 문제를 어떻게 이분탐색으로 여전히 모르겠어서 결국 정답봤다..

 

풀이 시나리오

1. 수직선 상에 N개의 마구간이 있다. '말의 마릿수(C) <= 마구간의 개수' 이므로 N개 마구간 중 C개에 말을 배치한다

2. 이 때 가장 가까운 두 마구간의 최대 거리를 구해야 한다. 즉, 말을 다 배치했을 때 각 말이 떨어진 최솟값(=가장 가까운 두 마구간의 거리)이 최대가 되도록 한다.

3. 그러므로 이분탐색으로 구할 값은 가장 가까운 두 말의 최대 거리이다. 즉, mid =가장 가까운 두 말의 최대 거리

4. 최대로 떨어뜨려야하는 만큼 가장 작은 좌표의 마구간에 말 한마리를 고정 배치하고, 구한 mid값은 말 한마리 당 거리로 가정했을 때 마구간에 말이 몇마리 들어갈 수 있는 지 체크(Count함수 정의 및 호출)

5. cnt > c라면 말이 너무 많이 들어갈 수 있으니 mid값을 늘려야 하므로 lt = mid + 1실행. cnt < c라면 말이 더 들어가야하므로 mid값을 줄여야 함. 따라서  rt = mid - 1실행. 그리고 cnt=c라면 들어갈 수 있는 말의 마릿수가 같은 한 mid값이 최대여야하므로 lt = mid + 1실행.

6. while문이 종료되면 결과값(최적의 mid값)출력

 

 

코드

n, c = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()

lt = 1
rt = h[-1]
res = 0


def count(m):
	#가장 낮은 번호의 마구간에 1마리를 배치했으므로 cnt=1로 시작
    cnt = 1
    prev = h[0]
    for i in range(1, n):
        if h[i] - prev >= m:
            cnt += 1
            #현재요소의 마구간 번호 - 처음 마구간 번호 >= mid값 이라면 step을 다시 카운트해야하므로 prev=현재 마구간
            prev = h[i]
    return cnt


while lt <= rt:
    mid = (lt + rt) // 2
    #분기문의 부등호를 결정하는 기준 -> 링크 참고
    if count(mid) >= c:
    	#lt를 증가시키는 상황 즉, 마릿수를 줄이기 위해 mid를 늘려야 할 때만 res에 mid를 넣는지 -> 링크 참고
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

 

이 문제 뿐만이아니라 이분탐색을 이용한 파라메트릭 서치 문제는 구현방법이 비슷한데 이번 글에서는 while문 내 분기문의 조건식 부등호를 결정하는 기준과 구한 mid값을 어떨 때 res에 저장해야하는지 설명하려고 한다

 

 

https://brotherstone.tistory.com/43

 

---

2024.2.13 여전히 풀지 못했다..^^ 다시 복습하도록  하자