악곱 == 악성곱슬

이분 탐색

---

이 문제는 주어진 리스트를 순서대로 나눠서 가장 공평한 크기로 나누려고 하는 것이 목적이다. 주어진 M개로 나눠야 한다. 따라서 직접 다 해보는 것부터 생각을 해보자

레슨 수는 최대 10만개, M은 최대 레슨개, 각 레슨의 길이는 최대 10000. 따라서, 일단 직접 다 해본다는 것은 조합으로 계산하면 10만 C M 이 된다. 그렇다면 10만을 보고 우리는 O(NlogN) 정도를 사용해야겠다는 것을 깨달아야 한다. 그래서 떠오른 것은 이분탐색, 우선순위 큐, 정렬 등이 있다.

여기서 정렬은 하면 안된다고 문제에서 주어진다. (순서대로 레슨이 진행되어야 한다) 그렇다면 우선순위큐, 이분탐색이 남는데,,, 이분탐색으로, 구간을 좁혀보면 될 것 같다는 생각을 할 수 있다. 그렇다면 구간의 최대값을 알아야 한다. 10^5 X 10^4 = 10^9. 하나의 블루레이에 들어갈 수 있는 최대값은 어림잡아 10^9가 나온다. 따라서 최소값을 0, 최대값을 10^9로 지정하여, 구간을 좁혀나가는 방식으로 구할 수 있다.

이 구간을 이용하여 10만개의 레슨을 순차탐색(O(N)) 하여 실제로 나눠지는 블루레이의 수를 구한다. 내가 구현한 코드에는 get_m으로 구현했다. 즉, 구한 get_m의 값과 실제 주어진 m 값을 비교해가며 최적의 값을 찾아가는 것이다. O(NlogN)

구현

---

import sys

def get_m(target):
    _sum, _cnt = 0, 1
    for i in range(len(lessons)):
        if lessons[i] > target:
            _cnt = INF
            break
        if _sum + lessons[i] > target:
            _cnt += 1
            _sum = lessons[i]
        else:
            _sum += lessons[i]
    return _cnt

def solution(start, end, m):
    answer = 0
    while start <= end:
        mid = (start + end) // 2
        if get_m(mid) > m:
            start = mid + 1
        else:
            answer = mid
            end = mid - 1
    return answer

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    INF = int(1e9)
    lessons = list(map(int, sys.stdin.readline().rstrip().split()))
    print(solution(0, INF, M))