[Python] 백준 16401 과자 나눠주기

1. 문제 - 백준 16401 과자 나눠주기

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

 

💡알고리즘 - 이분탐색

• 조카의 수 M (1 <= M <= 1,000,000), 과자의 수 N (1 <= N <= 1,000,000) -> 숫자의 크기가 굉장히 크다.
• 과자의 길이가 N개 주어지고, 각 과자를 여러개 나눌 수 있다는 가정 하에 막대 과자의 최대 길이를 구한다 -> 원하는 타겟이 있다.
• 숫자의 크기가 굉장히 큰 상황에서 특정 조건을 만족하는 값을 구해야하는 경우, 이분탐색을 활용한다.

✅ 풀이

m, n = map(int, input().split())
arr = sorted(list(map(int, input().split())))   # 이분 탐색을 위해 과자의 길이를 정렬한다.
start, end = 1, arr[-1]   # 과자의 길이는 양수이므로 start를 1, end를 arr의 최대값으로 설정한다.
answer = 0

while start <= end:
  mid = (start + end)//2
  cnt = 0
  for snack in arr:   # 나눠주고자 하는 과자의 길이가 mid일 때의 조카의 수
    cnt += snack // mid

  if cnt >= m:
    answer = mid
    start = mid + 1
  else:
    end = mid-1

print(answer)

여기서 중요한 점은 조건을 세우는 부분인데,

어떤 경우에 answer에 나눠주고자 하는 과자의 길이를 갱신하고, 과자의 길이를 조금 더 좁히거나 늘려야하는지를 고민해보아야 한다.

- cnt (나눠줄 수 있는 조카의 수)가 m보다 미치지 못한다면, 나눠주고자 하는 과자의 길이를 더 줄여야하므로 mid-1로 범위를 좁힌다.

- cnt가 m보다 크거나 같을 때 위와 반대로 생각하면 되는데, m을 충족하므로 우선 answer에 mid값을 갱신해나간다.