백준 2343번. 기타 레슨 (Python / 파이썬)

문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

문제 풀이

가능한 블루레이 크기 중 최소를 구하기 위해 이분탐색 알고리즘을 활용하였다. 

탐색해야 하는 값이 블루레이의 크기 이므로 블루레이 크기를 활용하여 start와 end값을 지정해주었다. 

이분 탐색은 mid 값을 구하여 탐색에 활용하므로 start와 end 값을 어떻게 정하느냐가 중요하다. 

 

start는 가능한 블루레이 크기 중 가장 작은 값이 되어야 한다. 

위의 그림과 같이 나눈다고 했을 때 블루레이의 크기는 9가 된다. 9보다 작은 값은 나올 수 없다. 

따라서 start의 값은 강의 시간 배열의 max값인 9로 설정해준다. 

 

end는 가능한 블루레이 크기 중 가장 큰 값이 되어야 한다. 

위의 그림과 같이 나뉘었을 때 블루레이의 크기는 45가 된다. 45보다 큰 값은 나올 수 없다. 

따라서 end의 값은 강의 시간 배열의 총 합인 45로 설정해준다. 

 

Step 1. start = 9, end = 45, mid = 27

블루레이 크기가 27보다 크면 안되므로 위의 그림과 같이 나눌 수 있다. 

하지만 블루레이의 개수가 3보다 작으므로 블루레이의 개수를 더 늘리기 위해 

mid값을 더 감소시켜야 한다. 따라서 end를 mid - 1로 설정해준다. 

 

Step 2. start = 9, end = 26, mid = 17

블루레이 크기가 17보다 크면 안되므로 위의 그림과 같이 나눌 수 있다. 

블루레이의 개수도 3개이므로 정답이 될 수 있다. 

따라서, 정답 변수에 일단 저장해놓고 최솟값을 더 탐색하기 위해 end를 mid - 1로 설정해준다. 

 

Step 3. start = 9, end = 16, mid = 12 

이번엔 블루레이의 개수가 5개이므로 너무 많다. 

따라서 start를 mid + 1로 설정해서 덜 나눠지도록 해준다. 

 

Step 4. start = 13, end = 16, mid = 14 

step 3와 동일하므로 start를 mid + 1로 설정해준다. 

 

Step 5. start = 15, end = 16, mid = 15

여전히 블루레이의 개수가 3개보다 많으므로 start를 mid + 1로 설정해준다. 

 

Step 6. start = 16, end = 16, mid = 16 

step 5와 동일하므로 start를 mid + 1로 설정해준다. 

 

Step 7. start = 17, end = 16

start가 end보다 커졌으므로 종료한다. 

 

이러한 과정을 통해 가능한 블루레이 크기 중 최솟값은 17임을 알 수 있다. 

---

My Code 

n, m = map(int,input().split())
time = list(map(int,input().split()))

start = max(time)
end = sum(time)

while start <= end:
    mid = (start + end) // 2 

    total = 0
    count = 1
    for t in time:
        if total + t > mid:
            count += 1
            total = 0
        total += t 

    if count <= m:
        ans = mid
        end = mid - 1
    else:
        start = mid + 1
    
print(ans)