[백준] 14627번 파이썬 _ 파닭파닭

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

14627번: 파닭파닭

파닭먹고싶다.

문제유형 : 이분탐색

 

문제풀이 :

• 이런 유형의 문제를 이미 알고있어서 보자마자 코드를 짰는데 웬걸 예외를 잡느라 8번은 더 제출했다...
• 날괴롭혔던 부분은 자를 파의길이가 0이되는,,, 즉 이분탐색에서 mid값이 0이되는 경우였다..ㅜ
  
  • 이해를 돕기위해 예시를 들면, 파의모든 길이를 더한만큼 치킨의 개수가 있다면 파를 길이1로 잘라야 모든 치킨에게 같은양의 파를 줄 수 있을것이다!!! (start = 0, end = 1이 되는경우)
  • 이경우에 mid값이 0이되는 상황이 발생한다. 이걸 힘들게 잡은 이유는 그동안 이분탐색 문제에서 mid값이 1까지 내려가는 경우는 잘 없었기 때문이다 ㅜㅡ 코드를 너무 템플릿처럼 기억하다보니 이런걸 잡 못잡는 상황이 발생한것같다. 
• 따라서 mid값이 0이 되는경우 예외적으로 다시 mid를 1 로 만들어서 길이 1로 잘라주는 과정이 필요했다는것.. 기억하자!!!'
• 하나더 참고하면 마지막에 남은파의양을 계산할때 총합에 치킨에 들어간 파를 빼는식으로 해야지 result를 나눈 나머지로 하면 안된당.

 

 

정답코드 :

import sys
input = sys.stdin.readline

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


start = 0
end = 1000000000

result = 0
while start<=end:
    mid = (start+end)//2
    if mid==0:
        mid = 1
    cnt = 0
    for i in pa:
        cnt += i//mid
    if cnt >= c:
        result = max(result, mid)
        start = mid+1
    else:
        #더 작게 잘라야함
        end = mid-1

# 총파의양 - 치킨*결정된 파의최대길이 = 라면에넣을 파
answer = sum(pa) - (c*result)
print(answer)