[알고리즘] BOJ 16401 과자 나눠주기 #Python

[BOJ] 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을 출력한다.

---

📍 풀이

💡 고찰

• 처음에는 힙(heap) 자료구조를 이용하여 문제에 접근하였다.
• 현재 가장 긴 막대 과자를 반으로 잘라 힙에 다시 추가하는 방식을 반복하였다.
• 코드를 제출하였지만 통과하지 못했고 현재 코드의 문제점을 찾기 위해 반례를 찾았는데, 수도 없이 많은 반례를 찾을 수 있었다.
• 이건 아무리 생각해도 힙으로 구현하는 것이 아닌 것 같아서 결국 구글링을 하였고 이진 탐색(Binary Search) 을 이용하여 문제에 접근하는 것임을 알게 되었다.

• 문제를 접했을 때 다른 문제들은 어떤 알고리즘을 활용해야 되는지 감이 오는데, 이진 탐색 문제는 감이 잘 오지 않는 것 같다.
• 이진 탐색 문제를 찾아서 여러번 풀어보고, 감을 찾아야 할 것 같다.

📌 문제 풀이

✏️ 1. 시작값과 끝값 설정

start, end = 1, max(L)

• 조카 1명에게 줄 수 있는 막대 과자의 최소 길이는 1이고, 최대 길이는 현재 가지고 있는 막대 과자의 최대 길이이다.

✏️ 2. 이진 탐색을 통한 조카 1명에게 줄 수 있는 막대 과자의 최대 길이 찾기

while start <= end:
    mid = (start + end) // 2
    if check(mid) >= M:
        start = mid+1
    else:
        end = mid-1

• mid 길이에 해당하는 막대 과자를 현재 주어진 막대 과자에서 몇개를 만들 수 있는 지 확인한다.
• 만약 mid 길이에 해당하는 막대 과자를 조카의 수(M)보다 많이 만들 수 있으면 mid 의 값을 늘리기 위해 start 에 mid+1 값을 할당한다.
• 반대로 mid 길이에 해당하는 막대 과자를 조카의 수(M)보다 적으면 mid 의 값을 줄이기 위해 end 에 mid-1 값을 할당한다.

✏️ 3. mid 길이로 만들 수 있는 막대 과자 개수

def check(mid):
    cnt = 0
    for length in L:
        cnt += length//mid
    return cnt

• 주어진 막대 과자(L)의 모든 원소를 mid 로 나눈 몫을 모드 더하여 값을 반환한다.

✍ 코드

from sys import stdin

# M명의 조카에게 줄 수 있는 막대 과자의 최대 길이
def solution(M, N, L):
    
    # mid 길이로 만들 수 있는 막대 과자 개수
    def check(mid):
        cnt = 0
        for length in L:
            cnt += length//mid
        return cnt

    # 시작과 끝 값
    start, end = 1, max(L)

    # 이진 탐색
    while start <= end:
        mid = (start + end) // 2
        if check(mid) >= M:
            start = mid+1
        else:
            end = mid-1
        
    return end

# input
M, N = map(int,stdin.readline().split())
L = sorted(list(map(int,stdin.readline().split())))

# result
result = solution(M, N, L)
print(result)