[백준/Python] #14627 파닭파닭

문제

 

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

14627번: 파닭파닭

---

Algorithm

이진탐색으로 해결했다. 여기서 이진탐색으로 구하고자 하는 값은 파닭에 넣을 파 한 조각의 길이이다. 파를 mid만큼 자를 때 만들 수 있는 파닭의 수 K는 각각의 파의 길이 O를 파닭에 넣을 파 한 조각의 길이의 추정값 mid로 나눈 몫의 합이고 라면에 넣을 파의 양은 O를 mid로 나눈 나머지의 합이다. 주문받은 파닭의 수가 C일 때 K가 C보다 크다면  라면에는 (K-C)*mid만큼 더 넣고 K=C가 된다. 이떄 mid의 최댓값을 찾는 과정이므로 K=C일 때는 K>C일 때와 같은 경우로 취급한다.

 

---

 

 

Code

import sys

input = sys.stdin.readline

def getOnions(x):
    a, b = 0, 0
    for o in onion:
        a += o // x
        b += o % x
        if a > C:
            loss = a - C
            a -= loss
            b += loss * x
    return a, b

S, C = map(int, input().split())

onion = []
for _ in range(S):
    onion.append(int(input()))

left = 1
right = int(1e9)

while left <= right:
    mid = (left + right) // 2
    chicken = 0
    chicken, _ = getOnions(mid)
    if chicken >= C:
        left = mid + 1
    else:
        right = mid - 1

_, ans = getOnions(right)
print(ans)