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

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

16401번: 과자 나눠주기

 

문제 해결

• 과자의 길이를 이분탐색으로 구하는 전형적인 이분탐색 문제
• 다만 길이를 구했다고 끝이 아니라 최대 길이를 구하는 것이므로 start <= end인 한 while문은 계속 돌아간다.

 

CODE

import sys
input = sys.stdin.readline
m, n  = map(int,input().split())
L = list(map(int, input().split()))
start = 1 # 과자의 길이는 1 이상
end = int(1e9)
answer = 0
while start <= end:
    mid = (start+end)//2
    c = 0 # 길이가 mid인 것을 만들 수 있는 개수
    for i in L:
        c += i//mid
    if c >=m:
        answer = max(answer,mid)
        start = mid + 1
    else:
        end = mid - 1
print(answer)