[BOJ - 이분탐색] 13702번 : 이상한 술집 ( python )

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

13702번: 이상한 술집

 

문제

프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용량이 802ml 이기도 1002ml가 나오기도 한다. 은상은 막걸리 N 주전자를 주문하고, 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 한다. 그런데 은상과 친구들은 다른 주전자의 막걸리가 섞이는 것이 싫어서, 분배 후 주전자에 막걸리가 조금 남아 있다면 그냥 막걸리를 버리기로 한다. (즉, 한 번 주문한 막걸리에 남은 것을 모아서 친구들에게 다시 주는 경우는 없다. 예를 들어 5명이 3 주전자를 주문하여 1002, 802, 705 ml의 막걸리가 각 주전자에 담겨져 나왔고, 이것을 401ml로 동등하게 나눴을 경우 각각 주전자에서 200ml, 0m, 304ml 만큼은 버린다.) 이럴 때 K명에게 최대한의 많은 양의 막걸리를 분배할 수 있는 용량 ml는 무엇인지 출력해주세요.

 

 

---

 

기본적인 이분탐색 코드와 거의 동일하다고 생각이 들었고,,

이전에 풀었던 나무 자르기와 상당히 유사한것은 푼 이후에 알았다.

 

1. 사고하기

• 목표 : N개의 주전자에 각각 다른 용량이 들어있고, K명에게 나누어 줄 때 최대값을 구하는 것.
• 유형 : [이분탐색]

최대한 많은 양을 찾아야 하는데

막걸리의 용량이 2^31 보다 작거나 같은 수 이므로 완전탐색할 수 없다 >> 이분탐색을 이용

• start = 1 , end = 주전자에 들은 용량들 중 가장 큰 값
• mid를 분배할 수 있는 용량으로 정했을 때, 각 용량을 mid 값으로 나눈 몫의 총합을 구한다.
• 총합이 k보다 크거나 같으면 일단 res 에 mid값을 저장해주고, 총합이 k보다 큰 경우에는 mid(분배용량)이 커져도 된다는 뜻이므로 start의 값을 키운다.
• 총합이 k보다 작으면 mid(분배용량)이 작아져야 한다는 뜻이므로 end의 값을 줄인다.
• 마지막에 res를 출력하면 정답!

 

2. 이 문제를 공유한 이유 : 파이썬 문법 중 처음 사용한 게 있어서!!!

 

 

정답 코드

#13702_이상한 술집_binary search_silver3

import sys
input = sys.stdin.readline

#주전자, 인원수
n, k = map(int,input().split())

li = [int(input()) for _ in range(n)]

start = 1
end = max(li)

res = 0
while(start<=end):
    mid = (start+end)//2
    count = 0
    
    count = sum(i//mid for i in li)
   
    #count가 많으니까 mid 가 커져도 됨. > start를 크게 
    if count >= k:
        res = mid 
        start = mid+1
    else: # count가 적으면 mid가 작아져야함. > end를 작게
        end = mid-1
        
print(res)