테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 기타 레슨 ======

===== 풀이 =====
  * 전형적인 [[ps:파라메트릭 서치]] 문제
  * 블루레이의 길이가 t일때, 강의들을 M개의 블루레이에 모두 넣을수 있는지를 체크하는 결정함수를 만들어서, 이분탐색으로 t의 최소값을 찾는다.
  * 결정함수는 그리디하게 강의들을 최대한 많이 현재 블루레이에 추가하고, 불가능한 경우 새 블루레이를 만드는 식으로 시뮬레이션 해서 필요한 블루레이가의 갯수가 M이하일때 참을 리턴하는 식으로 구현하면 된다. 결정함수의 시간 복잡도는 O(n)이다.
  * 다른 방식으로 결정함수를 구현하는 방법이 있다. 강의시간들의 누적합 배열을 만들고, i번째 블루레이까지에 들어갈수 있는 총 시간을 다시 이분탐색을 써서 찾는 방법이다. 1번째 블루레이에는 최대 t시간까지 들어갈수 있으므로, 누적합 배열에서 x이하의 최댓값을 이분탐색으로 찾는다. 이 값을 x[1] 이라 하면 이 값이 실제로 1번째 블루레이에 들어간 총 시간이 된다. 2번째 블루레이까지는 최대 x[1]+t 시간만큼 들어갈수 있다. 역시 누적합 배열에서 x[1]+t 이하의 최댓값 x[2]를 찾으면, 이 값이 실제로 2번째 블루레이까지 들어간 총 시간이 된다. 이것을 반복하면 M번째 블루레이까지 저장한 총 시간이 되고, 이것이 전체 시간보다 작으면 불가능한 것이다. 이경우 크기가 n인 누적합 배열에 대해서 이분탐색을 M번 수행하므로, 시간복잡도는 O(mlogn)이다.
  * 어느 쪽이 더 효율적일지는 m값에 따라서 다르겠지만, 제출 결과로는 후자가 더 빨랐다.
  * 블루레이의 길이 t의 탐색 범위는 [가장 긴 강의시간, 전체 강의시간의 합]으로 잡으면 된다. 이렇게 하면 총 시간 복잡도는 O(n*lognk) 또는 O(m*(logn)*(lognk))가 된다.


===== 코드 =====

==== 코드 1 - O(n)의 결정함수 ====
<dkpr py>
"""Solution code for "BOJ 2343. 기타 레슨".

- Problem link: https://www.acmicpc.net/problem/2343
- Solution link: http://www.teferi.net/ps/problems/boj/2343

Tags: [Parametric Search]
"""

from teflib import binsearch


def main():

    def is_valid(bluelay_len):
        bluray_count = 1
        cur_remaining_len = bluelay_len
        for l in lengths:
            if cur_remaining_len < l:
                bluray_count += 1
                cur_remaining_len = bluelay_len - l
            else:
                cur_remaining_len -= l
        return bluray_count <= M

    N, M = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    lengths = [int(x) for x in input().split()]

    beg, end = max(lengths), sum(lengths) + 1
    print(binsearch.minimum_valid_integer(beg, end, is_valid))


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - O(mlogn)의 결정함수 ====
<dkpr py>
"""Solution code for "BOJ 2343. 기타 레슨".

- Problem link: https://www.acmicpc.net/problem/2343
- Solution link: http://www.teferi.net/ps/problems/boj/2343

Tags: [Parametric Search]
"""

import bisect
from teflib import binsearch


def main():

    def is_valid(bluelay_len):
        pos = 0
        recorded_len = 0
        for _ in range(M):
            pos = bisect.bisect_right(acc_lengths,
                                      recorded_len + bluelay_len,
                                      lo=pos)
            if pos == N:
                return True
            recorded_len = acc_lengths[pos - 1]
        return False

    N, M = [int(x) for x in input().split()]
    lengths = [int(x) for x in input().split()]

    v = 0
    acc_lengths = [v := v + x for x in lengths]
    beg, end = max(lengths), sum(lengths) + 1
    print(binsearch.minimum_valid_integer(beg, end, is_valid))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:binsearch#minimum_valid_integer|teflib.binsearch.minimum_valid_integer]]

{{tag>BOJ ps:problems:boj:실버_1}}