[Python][백준] 18113_그르다 김가놈

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

18113번: 그르다 김가놈

문제

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

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

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

 

입력

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

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

 

출력

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

---

1.5 초 (추가 시간 없음) 이라는 제한이 있기 때문에, 최대 김밥조각의 길이 P를 완전탐색(Brute Force)로 찾아내는 것은 당연히 시간초과가 발생한다. (라는 것을 알면서도 첫 제출에서 완탐을 시도한 1인 ㅠ)

더 빠르게 적절한 P값을 찾아낼 수 있는 알고리즘이 바로 이분탐색법(Binary Search)이다.

 

M개 이상의 조각을 만들어 내는 최대 김밥조각의 길이 P를 찾아내자. --> 이분탐색

 

1번 예제로 자세히 살펴보면.

1) 1번에서 꼬다리를 손질하고 남은 김밥들의 길이는 kimbob = [8, 4] 이다. 

2) 즉, 김밥은 1cm ~ 8cm로 잘라볼 수 있고, binary 메소드에서는 처음에 이 중간값인 4cm로 김밥을 잘라본다.

3) 길이 8cm의 김밥은 4/ 4 로  2조각, 길이 4cm의 김밥은 4/ 1조각, 총 3조각으로 M을 만족시키지 않는다.

4) 즉, 더 작은 크기로 김밥을 잘라봐야 하므로 다시 2)으로 돌아가 1cm~4cm로 김밥을 잘라보자.

5) 1cm~4cm의 중간값인 2cm로 김밥을 잘라보면 2/ 2/ 2/ 2 4조각, 2/ 2 2조각으로 총 6조각 > M(4조각) 를 만족한다.

6) 5번의 결과는 조건을 만족하지만 답은 아니다. 중간값으로만 잘라봤을 뿐 더 최적의 P가 있을 수 있다(maxP를 구해야함).

--> 다시 2)로 돌아가 2cm보다 더 큰 3cm~4cm로 김밥을 잘라본다.

 

위의 과정을 통해 구한 maxP가 답이 되며, 꼬다리를 자른 뒤 남은 김밥이 없거나, 조건을 만족시키는 경우가 없다면 -1을 출력한다.

 

import sys

def binary(sta, end):
    global maxP

    if sta > end:
        print(maxP)
        return

    mid = (sta + end) // 2

    sum = 0
    for k in kimbob:
        sum += k // mid

    if sum >= M:
        maxP = max(mid, maxP)
        binary(mid+1, end)
    else:
        binary(sta, mid-1)

### MAIN
N, K, M = map(int, sys.stdin.readline().strip().split())

kimbob, maxP = [], -1
for _ in range(N):
    L = int(sys.stdin.readline())
    
    # 김밥 손질
    if L > 2 * K:
        kimbob.append(L - 2 * K)
    elif L > K and L < 2 * K:
        kimbob.append(L - K)


if len(kimbob) == 0 : # 전부 폐기하고 남은 김밥 없음
    print(-1)
    exit()

kimbob.sort()
binary(1, kimbob[-1])
 # 최소로 자를 수 있는 김밥조각의 크기 == 1
 # 최대로 자를 수 있는 김밥조각의 크기 == 제일 큰 김밥의 길이