문제

정래는 김밥가게 “그르다 김가놈”에 납품할 김밥을 만드는 김밥 공장을 운영한다. 정래는 김밥 양쪽 끝을 “꼬다리”라고 부른다. 그리고 꼬다리를 잘라낸 김밥을 “손질된 김밥”이라고 부른다.

공장에서는 김밥 N개에 대해서, 김밥 꼬다리를 잘라내고 손질된 김밥을 김밥조각으로 만드는 작업을 한다. 꼬다리를 잘라낼 때에는 양쪽에서 균일하게 K cm만큼 잘라낸다. 만약 김밥의 길이가 2K cm보다 짧아서 한쪽밖에 자르지 못한다면, 한쪽만 꼬다리를 잘라낸다. 김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다.

손질된 김밥들은 모두 일정한 길이 P로 잘라서 P cm의 김밥조각들로 만든다. P는 양의 정수여야 한다. 정래는 일정한 길이 P cm로 자른 김밥조각을 최소 M개 만들고 싶다. P를 최대한 길게 하고 싶을 때, P는 얼마로 설정해야 하는지 구하시오.

코드

import sys

input = sys.stdin.readline

n, k, m = map(int, input().split())
gimbaps = [int(input()) for _ in range(n)]

left = 1
right = max(gimbaps)
res = 0
rcnt = 0

def cutting (gimbap, p):
    if gimbap <= k:
        return 0
    elif gimbap < 2*k:
        gimbap -= k
    else:
        gimbap -= k*2

    return gimbap//p

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for gimbap in gimbaps:
        cnt += cutting(gimbap,mid)

    if cnt >= m:
        left = mid + 1
        res = mid
        rcnt = cnt
    else:
        right = mid - 1

if rcnt >= m:
    print(res)
else:
    print(-1)

설명

한쪽 꼬다리만 잘랐을 때 어떻게 해야 하는지 안 나와 있어서 생각을 좀 오래 했다. 이분탐색의 기준을 P로 두고 개수는 최소이고 값은 최대가 되도록 탐색했는데 이분탐색이 종료되고 김밥의 조각 개수가 m보다 작다면 -1 아니라면 이분탐색에서 구한 p 값(res)을 출력해주었다.