[Python] BOJ 2792 - 보석 상자(LJUBOMORA)

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

2792번: 보석 상자

# 이분탐색 문제는 문제를 보고 '이분탐색으로 풀어야겠다' 라고 떠올리는 게 힘들다..

# 비슷한 문제로는 https://www.acmicpc.net/problem/16401 '과자 나눠주기' 문제가 있다.

 

# jew에 보석의 개수를 입력받아 넣어주고 (1, max(jew))에서 binary_search를 실행시켜주면서

  최적의 값을 구한다.

 

# binary_search함수는 평소 이분탐색하듯이 짜면 되는데, tmp에 각각 보석의 개수를 mid값으로 나누고 

   올림한 값을 더해준다.(나머지가 있으면 사람 한명이 더 필요하므로)

   tmp값이 N보다 크면 low = mid+1을 통해 mid를 증가시키고, 

   N보다 작으면 mid를 감소시키고 dab에 dab과 mid중 작은 값을 넣어준다.

 

# 처음 low는 보석이 최소 1개는 있으므로 1로 설정하고,

    high는 입력된 보석의 개수 중 최댓값으로 설정했다.

 

import math, sys
input = sys.stdin.readline
N, M = map(int,input().split())
jew = []
for _ in range(M):
	jew.append(int(input()))

def binary_search(low, high):
	dab = 999999999
	while low <= high:
		tmp = 0
		mid = (low + high) // 2
		for i in jew:
			tmp += math.ceil(i / mid)
		
		if tmp > N:
			low = mid + 1
		else:
			high = mid - 1
			dab = min(dab, mid)
	return dab

print(binary_search(1, max(jew)))

(solved.ac 티어: 실버 3)

 

# Python은 느리니 되도록이면 pypy3로 제출하자.

# ZeroDivisionError가 발생할 수 있으니 low값은 1부터 시작하는 것이 좋다.