문제
https://www.acmicpc.net/problem/13702
접근
- 막걸리 주전자의 개수(s개)가 나누어줄 사람(c개)보다 작거나 같고, 정해진 용량을 나누어주고 남은 막걸리는 버린다고 했으므로, 나누어줄 수 있는 막걸리의 최댓값을 결정할 수 있다.
- 0과 최댓값 사이에서 문제의 제한조건을 만족시키는 경우를 찾아 나서면 되므로, 이분탐색으로 풀이
풀이
- lt를 1로, rt를 주전자에 들어있는 막걸리의 최솟값으로 설정
- mid 값에 대해서 각 주전자마다 몇 명에게 막걸리를 나눠줄 수 있는지 구해서, 총 몇명에게 막걸리를 나눠줄 수 있는지 계산하는 count 함수 작성
- count 함수의 값이 나누어줄 사람의 수 c보다 크거나 같을 경우, ans를 갱신하고 lt를 mid+1로 설정
- count 함수의 값이 나누어줄 사람의 수 c보다 작을 경우, rt를 mid-1로 설정
def count(x):
cnt = 0
for y in l:
cnt += y // x
return cnt
s, c = map(int, input().split())
l = [int(input()) for _ in range(s)]
lt = 1
rt = max(l)
ans = 0
while lt <= rt:
mid = (lt + rt) // 2
if count(mid) >= c:
ans = mid
lt = mid + 1
else:
rt = mid - 1
print(ans)
결과
'Python > Coding Test' 카테고리의 다른 글
1781 컵라면 (0) | 2022.02.10 |
---|---|
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |
11411 합 구하기 (0) | 2022.02.09 |
2110 공유기 설치 (0) | 2022.02.08 |