BOJ 16401번: 과자 나눠주기

호프 2021. 1. 25. 03:45

www.acmicpc.net/problem/16401

16401번: 과자 나눠주기

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN

www.acmicpc.net

아이디어:

막대 과자의 길이를 이분 탐색하여 조카 n명에게 줄 수 있는 과자 길이의 최댓값을 구한다.

import sys
m, n = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

high = 1000000000
low = 1
ans = 0

while (high>=low):
    mid = (high+low)//2
    num = 0
    for i in arr:
        num += i//mid
    if (num>=m):
        ans = mid
        low = mid + 1
    else:
        high = mid - 1
print(ans)