방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 나무의 수 및 길이가 각각 1,000,000 2,000,000,000 이므로 일반적인 방법으로는 문제를 해결할 수 없습니다. 즉 이분탐색을 진행해야 함을 알 수 있습니다. left를 1, right를 배열의 마지막 값으로 둔 뒤 이분탐색을 진행하면 쉽게 해결할 수 있습니다. 

단 이분탐색은 항상 리스트가 정렬 되어야 합니다. 따라서 오름차순으로 먼저 정렬한 뒤 위의 과정을 합니다.

소스코드

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ans = 0

left = 1
right = arr[n-1]

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

print(ans)