백준[1578] 세계 정복(파이썬)

이분 탐색 아이디어로 풀면된다. 주어지는 수가 최대 500억이므로 이분 탐색 문제임을 쉽게 떠올릴 수 있다.

 

k명씩 최대 몇개의 그룹을 만들 수 있는지 확인 한다(총 인구 수 // k)-> high

그룹은 최소 1개 이상 -> low

 

count는 현재 사이클에 차있는 그룹 수

cycle은 현재까지 그룹별로 차리한 횟수

 

만약에 설정한 그룹 수 보다 인구수가 많다면 cycle에 1을 더하고 넘어가면 된다.

n, k = map(int, input().split())
data = list(map(int, input().split()))

low = 1
high = sum(data) // k

from collections import deque
while low <= high:
    #print(low, high)
    q = deque(data)
    target = (low + high) // 2
    count = 0
    cycle = 0

    while q:

        x = q.popleft()
        if x >= target:
            cycle += 1
        else:
            count += x
            if count >= target:
                count = count % target
                cycle += 1

    if cycle >= k:
        low = target + 1
    else:
        high = target - 1

print(low - 1)