문제
https://www.acmicpc.net/problem/14627
14627번: 파닭파닭
첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에
www.acmicpc.net
풀이
시작(l)과 끝(r)을 1과 가장 긴 파의 길이로 두고, l이 r보다 작을 때까지 반복을 하여 이분탐색을 진행한다.
입력받은 파의 길이들을 중간 값인 mid로 나눈 몫을 cnt에 더해준다. (cnt : mid로 만들 수 있는 파닭 수)
만약 cnt가 주문받은 파닭의 수(c) 이상이라면, 파를 더 사용할 수 있다는 뜻이므로 l을 mid + 1로 갱신한다.
ans와 mid를 비교하여 더 큰 값으로 갱신한다.
cnt가 주문받은 파닭의 수(c) 보다 작다면, 파의 길이를 줄여야 하므로 r을 mid - 1로 갱신한다.
코드
import sys
input = sys.stdin.readline
s, c = map(int, input().split())
li = [int(input()) for _ in range(s)]
l, r = 1, max(li)
ans = 0
while l <= r:
cnt = 0
mid = (l + r) // 2
for i in li:
cnt += i // mid
if cnt >= c:
ans = max(ans, mid)
l = mid + 1
elif cnt < c:
r = mid - 1
print(sum(li) - (c * ans))