[16401] 과자 나눠주기

문제

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

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.
<br?
그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.


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


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

입력
3 10
1 2 3 4 5 6 7 8 9 10

출력
8

문제 정리

• 조카 들에게 최대한 긴 과자를 나눠주려고 한다.
• 조카들에게 다 같은 길이의 과자를 나눠줘야한다.
• 각각의 과자의 길이는 하나로 합칠 수는 없다.

이분탐색으로 접근해야 한다. 순차적으로 탐색하게 되면 시간초과가 발생한다.
1부터 특정한 길이를 찾아야 하기에 정렬이 따로 필요없는 이분탐색이다.

문제 풀이

m, n = map(int, input().split())
lengths = list(map(int,input().split()))
start = 1
end = max(lengths)
max_length = 0
while start <= end: # 종료 조건
    mid = (start + end) // 2 # 여기서는 찾아야 하는 최대 길이이다. 
    num = 0 # 과자의 개수
    # 몫나누기를 통해 과자를 특정 길이로 나눈 개수를 구할 수 있다.
    num = sum(length//mid for length in lengths)
    if num >= m : # 과자의 개수가 조카의 수를 넘거나 같다면 과자의 길이가 너무 짧거나 알맞다는 의미
        start = mid + 1 # 범위 재설정 start
        max_length = mid # max값 업데이트
    else: # 과자의 개수가 부족하다면 과자의 길이가 너무 길다는 의미
        end = mid - 1 # 범위 재설정 end 
print(max_length)

1/2씩 탐색범위를 줄여가며 가장 최적의 mid(과자의 길이)를 찾는다.
종료 조건은 start가 end보다 작은 시점까지이며
특정 길이가 아닌 종료 조건에 걸릴때까지 계속 탐색을 진행한다.
max_length는 0으로 초기화시켜 답이 없다면 0을 출력하도록 설정한다.

문제 후기

이분 탐색이라고 해서 정렬을 무조건 해야함은 아니다.
문제를 잘보고 종료조건을 어떻게 설정을 할지, 정렬을 해야할지를 선택해야한다.
아래는 첫 풀이였는데 while안에서 bisect를 통해 다시 찾다보니 시간초과가 발생하였다.

# 시간 초과 발생
from bisect import bisect_left
m, n = map(int, input().split())
lengths = list(map(int,input().split()))
lengths.sort()

start = 1
end = lengths[-1]
max_length = 0
while start <= end:
    mid = (start + end) // 2
    num = 0 # 과자의 개수
    idx = bisect_left(lengths, mid) # mid 이상의 특정 길이 이상의 과자를 찾기 위해
    while num < m and idx < n: # 과자가 더 이상 필요없어지는 지점까지 반복
        num += lengths[idx] // mid
        idx += 1
    if num >= m : # 과자의 개수가 조카의 수를 넘거나 같다면
        start = mid + 1
        max_length = mid
    else:
        end = mid - 1
print(max_length)