백준 알고리즘 2792: 보석 상자 (Python)

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

2792번: 보석 상자

---

문제 해결을 위한 과정

이 문제의 경우 N의 범위가 10^9 이므로 단일 for문으로 해결하려 해도 시간초과 판정을 받는 문제임을 알 수 있습니다. (파이썬의 경우 1초에 20,000,000번 연산을 한다 가정) 따라서 이분 탐색으로 진행합니다. 문제의 조건에서 보석을 받지 못하는 학생이 있어도 됨을 말했으므로 나눠준 보석을 받은 학생수가 N명보다 적어도 됩니다. 또한 같은 색상의 보석만 가져간다라는 조건이 있는데 이는 특별하게 고려하지 않아도 이분탐색 특성상 무조건 같은 색상의 보석만 준다는 것을 알 수 있습니다. 과정은 다음과 같습니다.

1) 보석 수 // 나누어 줄 보석 수 => 몫만큼 나누어준 학생수가 됨

2) 보석 수 % 나누어 줄 보석 수 => 나머지가 존재하면 1명의 학생에게 나누어 줄 수 있음.

---

소스코드

n, m = map(int, input().split())
arr = []
for _ in range(m):
  arr.append(int(input()))

arr.sort()
ans = int(1e9)

left = 1
right = arr[m-1]

while True:
  if left > right:
    break
  mid = (left + right) // 2
  temp = 0
  for i in range(m):
    temp += arr[i] // mid
    if arr[i] % mid != 0:
      temp += 1
  if temp > n:
    left = mid + 1
  else:
    ans = min(ans, mid)
    right= mid - 1
    
print(ans)