[백준/Python] 14627번 : 파닭파닭

문제

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

14627번: 파닭파닭

---

풀이

시작(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))