알고리즘💻/이분탐색&정렬&분할정복
BOJ 18113번: 그르다 김가놈
호프
2021. 8. 5. 14:43
https://www.acmicpc.net/problem/18113
18113번: 그르다 김가놈
첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다.
www.acmicpc.net
1. 입력을 받으면서 손질을 해준다. 이때 K보다 같거나 작은 길이는 그냥 버린다.
2. P의 길이를 low = 1, high = 10**9 로 하여 이분탐색한다.
import sys
input = sys.stdin.readline
N, K, M = map(int, input().split())
length = []
for _ in range(N):
L = int(input())
if (L>=2*K):
length.append(L-2*K)
elif (L>K):
length.append(L-K)
low = 1
high = 10**9
ans = -1
while (low <= high):
mid = (low+high)//2
tmp = 0
for i in length:
tmp+=i//mid
if (tmp >= M):
low = mid + 1
ans = max(ans, mid)
else:
high = mid - 1
print(ans)python은 시간초과가 나고 pypy3로 해야 통과한다.