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

문제

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

16401번: 과자 나눠주기

---

문제 요약

길이가 L인 막대 과자 N개가 있을 때, M명의 모든 조카들에게 같은 길이의 막대 과자를 나누어 줄 수 있다.

이 때 나누어 줄 수 있는 가장 긴 막대 과자의 길이를 출력한다.

 

+ 막대 과자는 길이와 상관없이 여러 조각으로 나누어 질 수 있지만, 과자를 하나로 합칠 수는 없다.

---

코드

M, N = map(int, input().split())
# M은 조카 수, N은 과자 수
arr = list(map(int, input().split()))
# 과자의 길이를 저장하는 리스트

start = 1
end = max(arr) # 가장 긴 과자 길이
# 이진 탐색의 시작 범위와 끝 범위

res = 0 # 나누어 줄 수 있는 막대 과자 최대 길이

while start <= end:
    mid = (start + end) // 2
    # 검사할 길이 mid

    total = 0
    # 길이 mid로 나누었을 때 조카들이 받을 수 있는 과자 개수

    for x in arr:
        if x >= mid:
        # 길이가 mid 이상인 과자가 있다면
            total += (x // mid) 
            # 과자 한 개를 길이가 mid인 과자 여러 개로 나눌 수 있기 때문

    if total >= M:
        # mid 길이로 나누어줄 수 있는 과자가 조카 수 이상이라면
        start = mid + 1 # 이진 탐색 범위를 좁혀 더 긴 길이도 가능한지 검사
        res = mid 
    else:
        end = mid - 1 # 이진 탐색 범위를 좁혀 더 작은 길이는 가능한지 검사

print(res)

---

코드 설명

1. 길이가 1일 때부터 입력 받은 막대 과자들 중 가장 긴 길이까지 조건에 맞는 값을 갱신하며 이진 탐색을 진행한다. (범위: start ~ end)

 

2. 탐색 범위의 중간 값인 mid는 조카들 수만큼 길이가 mid인 과자 여러개 나누어 줄 수 있는지 검사할 길이이다.

 

3. 과자 한 개를 여러 개로 나눌 수 있으므로 입력 받은 막대 과자 중 mid로 여러번 나눌 수 있는 과자가 있다면, 그만큼 조카들이 받을 수 있는 과자 개수는 증가한다.

 

4. 나누어 줄 수 있는 과자 수와 조카들 수를 비교하여 이진 탐색 범위를 조정한다.

 

5. start가 end보다 커지면 탐색을 종료한다.