[백준]18113. 그르다 김가놈

문제(18113. 그르다 김가놈)

김밥의 꼬다리를 제거한 김밥을 손질된 김밥 L이라 한다.
김밥은 양쪽 꼬다리를 균일한 Kcm만큼 잘라낸다. 만약 김밥의 길이가 2Kcm보다 짧으면 한쪽 꼬다리만 제거하고 김밥의 길이가 K보다 작거나 같으면 폐기한다.
손질된 김밥을 최대 Pcm로 최소M개를 만들려고 할 때, 최대 P를 찾아라.
만족하는 P가 없으면 -1을 출력
P는 양의 정수이다.

아이디어

문제를 잘 읽어야 풀 수 있다. 구현 난이도는 어렵지 않으나 문제의 내용이 애매하며 예제또한 애매하게 알려줘서 한번에 맞추기가 매우 어려운 문제이다.
내가 생각한 핵심아이디어는 김밥의 폐기조건을 정확하게 이해하고 구현해야한다.

김밥의 폐기조건
1.  L <= K
2. L == 2K

1번 폐기조건은 쉽게 생각할 수 있지만 2번은 왜라는 생각이 들 수도 있다.
문제에서 2K보다 작으면 K만 제거하고 K보다 작거나 같으면 폐기이다.
그러면 2K와 L이 같은 경우에는 한쪽만 자르는가 양쪽다 자르는가? 정답은 양쪽다 잘라야한다. 2K보다 짧지 않기 때문이다.(문제를 잘 읽자) 이러한 폐기조건을 알았다면 나머지는 이분탐색으로 어렵지 않게 구현할 수 있다.

---

코드

import sys  
import bisect  
input = lambda : sys.stdin.readline()  

N, K, M = list(map(int, input().split()))  
arr = []  
L_set = set()  
for _ in range(N):  
L = int(input())  
if L <= K or L == 2 * K:  
continue  
if L < 2 * K:  
arr.append(L - K)  
L_set.add(L - K)  
else:  
arr.append(L - 2 * K)  
L_set.add(L - 2 * K)  

if not arr or sum(arr) < M:  
print(-1)  
elif len(L_set) == 1 and sum(arr) >= M:  
print(arr[0])  
else:  
n = len(arr)  
arr.sort()  
l = 1  
r = arr[-1]  
while l < r:  
c = (l + r) // 2  
cnt = 0  
i = 1  
while arr[-1] >= c * i:  
index = bisect.bisect_left(arr, c * i)  
cnt += (n - index)  
i += 1  

if cnt >= M:  
l = c + 1  
else:  
r = c  

print(l-1)