[Python/파이썬] 백준 18113번 그르다 김가놈

18113번: 그르다 김가놈

 

문제

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

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

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

입력

첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ $10^6$, 1 ≤ K, M ≤ $10^9$, N, K, M은 정수)

두 번째 줄부터 김밥의 길이 L이 N개 주어진다. (1 ≤ L ≤ $10^9$, L은 정수)
 

 

출력

김밥조각의 길이 P를 최대로 할 때, P를 출력한다. 만족하는 P가 없는 경우, -1을 출력한다.

코드

import sys
input = sys.stdin.readline

n, k, m = map(int, input().split())
gimbabs = []
for _ in range(n):
    length = int(input())
    if length <= k:
        continue
    if length < (k*2):
        length -= k
    else:
        length -= (k*2)
    if length == 0:
        continue
    gimbabs.append(length)

if not gimbabs:
    print(-1)
else:
    start, end = 1, max(gimbabs)
    ans = -1
    while start <= end:
        p = (start + end) // 2
        res = 0
        for gb in gimbabs:
            res += (gb//p)
        if res < m:
            end = p-1
        else:
            start = p+1
            ans = p
    print(ans)

초기값 start, end를 각각 1과 꼬다리를 잘라내고 남은 쓸 수 있는 김밥들 중 가장 긴 김밥의 길이로 하고 이분탐색을 통해 가능한 p의 길이를 구한다. 

 

PyPy3로는 통과하고 Python3로는 시간 초과가 발생하는데 아마 p로 잘랐을 때 가능한 김밥조각의 개수를 구하는 과정 때문에 시간 초과가 발생하는 것 같다.