[2792] 보석상자 in python

> 이분탐색

 

 

평소에는 이분탐색을 풀 때

cnt==n일때,

cnt<n일때,

cnt>n일때

각각 조건을 나눠 계산을 진행해줬다.

 

그러나

이번 문제처럼 최솟값이나

혹은 최댓값을 구할 땐

위 방식보다는

아래 코드와 같이 작성을 해야한다.

 

if cnt > n:
    left = mid + 1
else:  # cnt<=n
    right = mid - 1
    result = min(result, mid)

 

 

이 문제에서는

질투심이 최소가 되게 보석을 나눠줘야한다.

그러려면 주어진 학생의 수만큼

모든 학생들에게 보석을 나눠주어야한다.

 

 

보석의 개수가 담긴 배열이

[1,4,4,7,7] 이라고 가정한다.

학생의 수는 5명이다.

 

left = 1, 

right = 7,

mid= (1+7)//2 = 4

 

최대 4개의 보석을 각각의 사람들에게 모두 나눠주면

[1,4,4,4,4,3,3] 7명의 사람들에게

빠짐없이 나눠줄 수 있다.

 

하지만 우리가 줄 수 있는 학생의 수는 5명이다. 

나눠주는 보석의 수(mid)가

4보다 더 커야하므로

left의 값에는 mid+1이 되어야한다. 

 

 

만약 줄 수 있는 학생의 수보다

작은 수나 같은 수가 나오면?

mid의 값이 작아져야한다.

그래야 많은 사람들에게 최대한 나눠줄 수 있기 때문이다.

 

 

 

 

 

 

n, m = map(int, input().split())  # 학생수, 보석수
array = [int(input()) for _ in range(m)]
left = 1
right = max(array)
result = 10 ** 9
while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for i in array:
        idx = 0
        if i <= mid:
            cnt += 1
            continue
        if i % mid == 0:
            cnt += i // mid
        else:
            cnt += i // mid + 1
    if cnt > n:
        left = mid + 1
    else: # cnt<=n
        right = mid - 1
        result=min(result,mid)
print(result)

 

 

 

 

이번 문제와 비슷한 형식이어서

참고하기 위해 저장

 

https://eboong.tistory.com/485

[2805] 나무 자르기 in python