[BOJ] 16401. 과자 나눠주기

문제

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

• M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이
• 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다
• 첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.
• 단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

 

---

 

주요 아이디어

• 과자 최대 길이를 이분탐색 target으로 두기
• target mid 값을 기준으로 나눠줄 수 있는 개수 구하기
  • 개수 모자랄 경우 최대 길이 줄이기
  • 개수 많을 경우 최대 길이 늘리기

 

---

 

코드 구현 (Python 3)

 

"""
과자 최대 길이를 이분탐색 target으로 두기
"""
m, n = map(int, input().split())
cookies = list(map(int, input().split()))
cookies.sort()

start, end = 1, cookies[-1]
target = 0 # 안될경우 0 출력


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

    total = 0

    # m명한테 줄 수 있는지 아닌지도 판단해야 함
    # mid 값을 기준으로 나눠줄 수 있는 개수 구하기
    for c in cookies:
        # 10 // 7 = 1
        if c >= mid:
            total += c // mid

    # 범위 늘리기
    if total >= m:
        target = mid
        start = mid + 1
    else:
        end = mid - 1

print(target)

 

 

---

 

제출 결과