[ 2343 ] [ 이분 탐색 ] 기타 레슨

문제 설명

---

문제

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 레슨의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 레슨의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)로 주어진다. 각 레슨의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

---

풀이 과정

1. blueray의 길이를 절반씩 조사한다.
   • 초기 범위를 레슨들중 최대 길이 ~ 100000 * 10000으로 설정(최대 레슨의 길이 * 최대 레슨의 수)
   • 중간 길이 middle에 대해서
     1. 전체 레슨들을 듣는데 몇개의 blueray가 필요한지 계산
     2. blueray의 개수가 M보다 작거나 같다면, 길이의 최솟값을 구해야 하므로 정답 저장 후 왼쪽 구간에 대해서 진행
     3. blueray의 개수가 M보다 크다면 길이를 늘려야 하므로, 오른쪽 구간에 대해서 진행

틀렸던 점

1. blueray의 초기 범위를 0부터 했다가 틀림.
   • 레슨이 10이라고 할때, blueray를 5 5로 할 수 없음.
2. 처음에는 blueray의 개수가 M과 같을때만 정답에 저장하였으나.. M보다 작거나 같을때로 수정하여야 함.
   • M보다 작다면 맞출 수 있으므로
     • M = 2, [1, 2, 3] 이라고 할 때
     • 예시로 길이가 6일때 [1, 2, 3] 모두 포함되나..
     • 1에다가 blueray 하나를 통째로 주고 [2, 3]에 blueray 하나를 주는 방식으로 두개 맞출수 있음.

---

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
lessons = list(map(int, input().rstrip().split()))

left = max(lessons)
right = 100000 * 10000

answer = max(lessons)

while left <= right:
    # middle : blueray의 길이
    middle = (left + right) // 2

    blueray = 1
    current = middle

    # blueray의 길이가 middle일때 몇개 나오는지 
    for lesson in lessons:
        if current - lesson < 0:
            blueray += 1
            current = middle - lesson
        else:
            current = current - lesson

    # blueray의 길이가 M보다 작다면 정답 저장 후 blueray를 줄여야 함
    # blueray의 길이가 M보다 크다면 blueray를 늘려야 함
    if blueray <= M:
        answer = middle
        right = middle - 1
    elif blueray > M:
        left = middle + 1

print(answer)