Koala - 10기/코딩테스트 준비 스터디

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

future0610 2023. 4. 1. 21:57

문제

 

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


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)