[백준/Python]14627번 - 파닭파닭

문제

백준 14627번 - 파닭파닭

해결 과정

• 이분탐색 이용
• 이분탐색을 이용하기 위해 파의 길이 정렬
• slice 함수
  • 매개변수로 파닭에 들어가는 파의 길이 len, 사온 파의 길이가 들어있는 배열 scallion을 받는다.
  • 반복문을 돌면서 파닭에 들어가는 파의 개수를 계산 후 반환한다.
• 시작점은 1, 끝점은 max(scallion), 찾으려는 데이터의 초기값은 0
• 반목문을 통해 이분 탐색한다.
  • 파닭에 들어가는 파의 길이가 중간값일 때
  • 파의 개수가 파닭의 수보다 크거나 같으면
    • 파의 개수는 항상 파닭의 수를 넘지 않는다. 조건에 의해
    • 파의 길이(maxS)가 더 길어져야 파의 개수가 줄어드니까
    • 시작점 = 중간점+1
  • 파의 개수가 파닭의 수보다 작다면
    • 파의 길이(maxS)가 더 짧게해야 파의 개수가 늘어나니까
    • 끝점 = 중간점-1

시행착오

• 시작점과 끝점 초기값 설정이 힘들었다.

풀이

import sys
s, c = map(int,sys.stdin.readline().split())
scallion = [int(sys.stdin.readline()) for _ in range(s)]

scallion.sort()

# 파닭에 들어가는 파의 개수
def slice(len, scallion):
  cnt = 0
  for i in scallion:
    cnt += i // len
  return cnt
  
start = 1
end = max(scallion)
# 파닭에 들어가는 최대 파의 길이
maxS = 0

while end >= start:
  mid = (end + start) // 2
  # 파닭에 들어가는 파의 개수가 파닭의 수보다 크거나 같다면
  if slice(mid, scallion) >= c:
    maxS = mid
    start = mid + 1
  # 파닭에 들어가는 파의 개수가 파닭의 수보다 작다면
  else:
    end = mid - 1

# 라면에 들어가는 파의 양 = 전체 파의 양 - 사용한 파의 양
answer = sum(scallion) - maxS * c
print(answer)

• 파의 길이 (start, end, mid)

start	end	mid
1	440	220
1	219	110
111	219	165
166	219	192
166	191	178
166	177	171
172	177	174
175	177	176
175	175	175