[코딩테스트] 이상한 술집

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

문제부터 분석을 해보죠

일단 시간 제한은 1초에, 메모리 제한은 512MB입니다. 그리고 N은 10000까지 제한이 되어있는데, 이론상 시간 제한은 1초이기 때문에 $O(N^2)$ 의 복잡도까지 가능은 합니다.

그러나 최대한 많은 양의 막걸리를 분배할 수 있는 용량 을 구하는 것이 문제이기 때문에, 이분탐색을 시행해야합니다. 따라서 저는 $O(N^2logN)$ 의 복잡도로 문제를 해결할겁니다.

풀이는 쉬우니 바로 따라오시죠

코드부터 봅시다

import sys

# 13702 이상한 술집
input = sys.stdin.readline

N, K = map(int, input().split())
alchohol_list = []

for i in range(N):
    alchohol_list.append(int(input()))
    
start, end = 1, max(alchohol_list)

while start <= end:
    mid = (start + end) // 2
    count = 0
    
    for alchohol in alchohol_list:
        count += (alchohol // mid)
    
    if count >= K:
        start = mid + 1
    else:
        end = mid - 1
        
print(end)

일단 count의 경우에는 몇 번 나눌 수 있는지 누적할 변수입니다.

그리고 이분탐색의 과정에서, alchohol_list를 선형으로 탐색하여 count에 값을 반영한 뒤 count의 값을 바탕으로 start를 늘리거나, end를 줄이는 방식으로 이분탐색을 수행합니다.

마지막에는 end를 출력시켜서 문제를 마무리합니다.