[이진탐색] 백준_파닭파닭

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

14627번: 파닭파닭

이 문제를 풀기 위한 아이디어는 이진탐색범위와 탐색기준을 제대로 설정하는 것입니다!

이진탐색범위 : 파의 길이 1~가장긴파의길이
이진탐색기준 : mid길이로 잘랐을 때 파닭의 수가 padack_cnt보다 크면, mid를 더 크게 잘라서 파닭의 수를 줄여야하므로 오른쪽탐색(start=mid+1), mid길이로 잘랐을 때 파닭의 수가 padack_cnt보다 작으면, mid를 더 적게 잘라서 파닭의 수를 늘려야하므로 mid를 줄이기 위해 왼쪽 탐색(end=mid-1)

import sys
input=sys.stdin.readline

pa_cnt, padack_cnt = map(int, input().split())
pa_length=[]
for i in range(pa_cnt):
  pa_length.append(int(input()))

answer=0
start=1
end=max(pa_length)

while(start<=end):
  mid=(start+end)//2 #mid는 미래의 정답(여기선 파닭 하나당 넣을 수 있는 최대 파의 길이)

  #이진탐색범위 : 파의 길이 1~가장긴파의길이
  #이진탐색기준 : mid길이로 잘랐을 때 파닭의 수가 padack_cnt보다 크면, mid를 더 크게 잘라서 파닭의 수를 줄여야하므로 오른쪽탐색(start=mid+1), mid길이로 잘랐을 때 파닭의 수가 padack_cnt보다 작으면, mid를 더 적게 잘라서 파닭의 수를 늘려야하므로 mid를 줄이기 위해 왼쪽 탐색(end=mid-1)
  cnt=0
  for i in pa_length:
    cnt+=i//mid

  if cnt >= padack_cnt:
    answer=mid
    start=mid+1
  else:
    end=mid-1

print(sum(pa_length)-(answer*padack_cnt))

주의할 점은 남은 파를 출력할 때 절대로 나머지로 계산하면 안 된다는 점입니다!

만약, 이 문제를 틀렸다면 나머지로 계산하셨을 거 같아요!

반례는 다음과 같습니다.

3 5
10
10
10

다음과 같은 입력이 주어졌을 때, 파닭을 5개로 만들기 위해 5만큼 씩 잘라서 10-5*2, 10-5*2, 10-5*1로 잘라서 5를 남겨서 출력해야하는데요. 나머지로 하면 나누어 떨어져서 0을 출력하기 때문에 틀렸다고 나옵니다.

제가 푼 코드처럼 (파의 길이의 합 - 파를 자를 최대길이*파의 개수)로 구해주세요!