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

문제

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

백준 문제집 - 0x13강 - 이분탐색

 

알고리즘: 이분 탐색

---

풀이

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.
조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.
그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.
M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.
단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

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

막대과자의 길이가 나누고자 하는 길이보다 길다면 자를 순 있지만 합칠 순 없다.

예제 1로 보면,

3 10
1 2 3 4 5 6 7 8 9 10
# 답: 8

조카 3명에게 동일한 길이의 막대과자를 나누어줘야하므로, 8, 9, 10 을 8에 맞춰 자르는것이 최대길이다.

하지만 정답이 항상 리스트 내에 존재하는건 아니다.

 

아래는 예제 2다.

4 3
10 10 15
# 답: 7

4명에게 동일한 길이로 나눠주려면 7만큼씩 부러뜨려야한다.

10//7 = 1

10//7 = 1

15//7 = 2

 

따라서 이분탐색으로 1부터 가장 큰 막대의 길이만큼을 탐색한다.

두 값을 더한 뒤 반으로 나눠 mid를 구하고, 이 길이만큼 막대과자를 모두 나눈다.

나눈 막대과자의 갯수가 조카의 수 M과 같거나 크다면 ret을 mid로 갱신한 후 start를 mid + 1으로, 작다면 end를 mid - 1로 변경 후 다시 탐색한다.

start와 end가 일치할때까지 위 과정을 반복한다음 최종적으로 ret을 출력한다.

 

전체 풀이

# 메모리: 146176KB / 시간: 4768ms
from sys import stdin


input = stdin.readline

M, N = map(int, input().split())
snacks = sorted(map(int, input().split()))

start, end = 1, snacks[-1]
ret = 0

while start <= end:
    mid = (start + end) // 2

    # mid길이만큼 과자를 잘라 M개로 만들 수 있다면 성공
    cnt = sum(snack//mid for snack in snacks)

    if cnt >= M:
        ret = mid
        start = mid + 1
    else:
        end = mid - 1

print(ret)