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

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

문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

 

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

 

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

 

소스코드

M, N = map(int, input().split())
L = sorted(list(map(int, input().split())))
left, right = 1, L[-1]
result = 0

while left <= right:
    cnt = 0
    mid = (left + right) // 2
    for length in L:
        cnt += length // mid #또는 cnt = sum(length // mid for length in L)

    if cnt >= M:
        result = mid
        left = mid + 1
    else:
        right = mid - 1

print(result)

 

풀이

-이진탐색(Binary search)으로 풀이

1. M과 N을 입력받는다.

2. 길이 L을 입력받고 정렬한 상태로 저장한다.

3. 막대과자의 길이는 양의 정수여야 하므로 left를 1로 초기화한다. right는 길이 L의 최댓값인 L[-1]로 설정한다. 답을 출력할 때 사용할 result는 불가능한 경우에 0을 출력하므로 0으로 초기화한다.

4. left와 right의 중간값인 mid를 막대과자의 길이라고 가정하고, 리스트 L의 모든 요소들에 대하여 mid가 길이일 때의 개수(cnt)를 계산한다.

5. cnt가 조카수 M보다 크거나 같을 경우, 조건을 충족하므로 result에 저장하고 left값을 mid + 1로 증가한다.

6. 작을 경우에는 right의 값을 mid - 1로 감소하여 범위를 줄인다.

7. result를 출력한다.