[Python/파이썬] 백준 14627번 파닭파닭

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

코드

import sys
input = sys.stdin.readline

s, c = map(int, input().split())
green_onion = [int(input()) for _ in range(s)]

answer = 0
l, r = 1, max(green_onion)
while l <= r:
    mid = (l+r)//2

    chicken = 0
    ramyeon = 0
    for go in green_onion:
        chicken += go // mid
        ramyeon += go % mid

    if chicken >= c:
        l = mid+1
        answer = ramyeon + (chicken-c)*mid
    else:
        r = mid-1

print(answer)

 

이 문제는 조건을 만족하는 값 중 최대 값을 구하는 문제이기 때문에 파라메트릭 서치 알고리즘으로 풀 수 있는 문제이다. 여기서 조건은 다음과 같다.

- 각 파닭에 같은 양의 파를 넣는다.

- 하나의 파닭에는 하나의 파만 들어간다.

 

파라메트릭 서치에서는 조건을 만족하는지 확인하고, 만약 확인한다면 가능한 더 작은 범위로 좁혀서 탐색하는 것을 반복하며 최적의 해를 찾는다. 여기서는 다음의 코드로 조건을 만족하는지 확인한다. `mid`가 파닭에 들어가는 하나의 파의 길이이다.

chicken = 0
ramyeon = 0
for go in green_onion:
    chicken += go // mid
    ramyeon += go % mid

if chicken >= c:
    l = mid+1
    answer = ramyeon + (chicken-c)*mid
else:
    r = mid-1

 

모든 파를 `mid` 길이로 썰었을 때, 주문받은 파닭 수(`c`) 이상 만들 수 있는지 확인한다.

만약 만들 수 있다면 현재 c마리에 각각 `mid`만큼 넣어주고 남은 파를 `answer`에 저장하고, `l = mid+1`로 탐색 범위를 줄인다.

만들 수 없다면 r = mid-1로 각 파닭에 들어가는 파의 길이를 줄이는 쪽으로 탐색 범위를 줄인다.

 

이 과정을 `l`과 `r`이 같아질 때까지 반복하고 나서 `answer`의 값이 각 파닭에 조건을 만족하도록 파를 넣고 나서 남은 파의 길이, 즉 라면에 넣을 파의 길이이다.