이분 탐색 응용문제로 올바른 사고 연습하기2

1. 문제

 

18113번: 그르다 김가놈 (acmicpc.net)

18113번: 그르다 김가놈

 

2. 풀이

 

문제를 보면 김밥의 길이가 k보다 큰 경우, 양쪽을 균일하게 k씩 자른다

 

하지만 2k보다 짧은 경우, 한쪽 k만 자른다.

 

k보다 작거나 같은 경우 김밥은 그냥 폐기한다

 

김밥 길이를 받을 때, L > k인 경우, L < 2k일때 L-k를 리스트에 저장하고, L > 2k일때, L-2k를 리스트에 저장한다

 

L == 2k일때는 문제에서 아무런 언급이 없기때문에 폐기해야된다고 추측하는게 적절한것 같다

 

n,k,m = map(int,stdin.readline().split())

kimbob = []

for i in range(n):
    
    L = int(stdin.readline())

    if L > k:
        
        if L < 2*k:
            
            kimbob.append(L-k)
        
        elif L > 2*k:
            
            kimbob.append(L-2*k)

 

이 과정을 거쳤을때, 리스트 kimbob에 들어있는게 없으면 P는 찾을 필요도 없이 존재할 수 없을 것이니 -1을 출력하고

 

그렇지 않다면 이분탐색으로 P의 최댓값을 찾는다

 

P의 최댓값을 어떻게 찾을 수 있을까?

 

P가 가능한 범위가 어딘지를 먼저 생각해보자

 

문제는 kimbob에 들어있는 kimbob을 모두 일정한 길이 P로 자른다

 

모두 동일한 길이 P로 잘라야하니.. P는 아무리 커봐야 kimbob에 든 원소의 최댓값까지 가능할 것이다

 

또한 P는 양의 정수이므로 1 이상이다

 

근데 P는 kimbob에서 가장 작은 원소까지만 가능한거 아닌가?

 

예를들어 kimbob의 원소중 4cm가 있는데 P = 7cm라면??? 그럼 그냥 그 kimbob은 P로 자르면 0cm가 된다(라고 생각하면 된다)

 

def binary_search(array,m,start,end):

    max_m = sum(array)
    
    while start < end:
        
        mid = start + (end - start)//2

        total = 0

        for k in array:
            
            total += k//mid
            
             
        if total >= m:

            start = mid + 1

        else:
            
            end = mid
    
    if end == 1:
        
        if max_m < m:
            
            return -1

    return end - 1

 

들어오는 배열의 합은 1번만 구하기 위해 미리 구해놓고,

 

start와 end의 중간값 mid가 선택한 P이다

 

김밥을 P로 자른다는 것은, 김밥의 길이 k를 P로 나누는 것이다.

 

P로 나눌때, 그 몫이 해당 김밥을 P로 자를때 얻을 수 있는 김밥조각의 개수

 

모든 김밥에 대해 mid로 나눠보고 그 몫의 합을 total이라고 한다면, total이 최소 m이 되는지를 조사해야한다.

 

 

total이 m 이상이라면? 해당 mid는 조건을 만족하며, mid 이후로도 가능성이 있다.

 

최대 P를 구해야하므로 start를 mid+1로 이동

 

total이 m보다 작거나 같다면? 해당 mid는 조건을 만족하지 않으며, 이는 mid가 너무 크니까 total이 작다는 뜻이다

 

따라서 end를 mid로 이동해서 해당 mid보다 작은 부분에서 탐색을 진행

 

 

 

반복문이 끝났을때, end가 1이라면?

 

모든 김밥을 길이 1로 잘라본다. 이는 김밥 길이의 총합 = 나올 수 있는 김밥 조각의 개수가 된다

 

이 김밥 길이의 총합이 m보다 작다면, 길이 1로 잘라도 최소 m개를 얻을 수 없다는 뜻이므로 -1을 return

 

그렇지 않다면 total >= m일때, mid가 가능성 있고 start = mid + 1로 이동시켰으므로,

 

start = end일때 반복문을 탈출했으며, 구하고자 하는 값은 mid에 있으니까 end - 1을 return해야한다.

 

from sys import stdin

def binary_search(array,m,start,end):

    max_m = sum(array)
    
    while start < end:
        
        mid = start + (end - start)//2

        total = 0

        for k in array:
            
            total += k//mid
            
             
        if total >= m:

            start = mid + 1

        else:
            
            end = mid
    
    if end == 1:
        
        if max_m < m:
            
            return -1

    return end - 1

n,k,m = map(int,stdin.readline().split())

kimbob = []

for i in range(n):
    
    L = int(stdin.readline())

    if L > k:
        
        if L < 2*k:
            
            kimbob.append(L-k)
        
        elif L > 2*k:
            
            kimbob.append(L-2*k)

if kimbob == []:
    
    print(-1)

else:
    
    kimbob.sort()

    print(binary_search(kimbob,m,1,kimbob[-1]+1))