[백준/python] 2343번: 기타 레슨

문제

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

---

문제 요약

N개의 강의 영상들을 같은 크기 M개의 블루레이에 저장할 때, 가능한 블루레이의 크기 중 최소 크기를 출력한다.

 

+ 강의를 블루에이에 저장할 때 강의의 순서가 바뀌면 안된다 (정렬 X)

---

코드

N, M = map(int, input().split())

arr = list(map(int, input().split()))

start = 0
end = sum(arr)
# 이진 탐색 범위

res = sum(arr)
# 최소 블루레이 크기 (초기값: 1개 블루레이에 모든 강의를 저장할 경우)

while start <= end:
    mid = (start + end) // 2
    # 탐색하는 블루레이 크기

    if mid < max(arr):
    # 크기가 가장 큰 강의를 담을 수 없다면
        start = mid + 1
        # 탐색 범위 재설정
        continue

    cnt, tmp = 1, 0
    # cnt는 사용된 블루레이 개수, tmp는 현재 블루레이의 용량

    # 입력 받은 강의들을 블루레이에 넣어 보며 확인
    for num in arr:
        if tmp + num <= mid:
        # 현재 탐색하는 블루레이의 용량을 초과하지 않으면
            tmp += num
            # 현재 블루레이에 저장
        else:
        # 용량을 초과하면
            tmp = num
            cnt += 1
            # 새로운 블루레이에 저장

    if cnt <= M:
    # 사용된 블루레이 개수가 M이하라면
        end = mid - 1
        # 더 작은 크기의 블루레이를 사용할 수 있는지 탐색
        res = min(res, mid)
        # 이전까지의 탐색했던 블루레이보다 더 작은 크기라면 res값 갱신
    else:
    # 사용된 블루레이 개수가 M초과라면
        start = mid + 1

print(res)

---

코드 설명

1. start ~ end 범위를 이진 탐색을 하며 영상을 담을 블루레이의 크기의 최소값을 찾는다.

 

+ start의 초기 값은 0, end의 초기 값은 모든 영상들의 크기를 더한 값이다. (1개의 블루레이 1개로 모든 영상을 담는 경우)

 

2. start와 end의 중간 값인 mid는 현재 탐색하고 있는 블루레이의 크기이다.

 

3. mid 값이 가장 긴 강의 길이보다 작다면, 어짜피 mid 크기의 블루레이들로는 강의들을 모두 담을 수 없으므로 더 큰 mid 값으로 탐색 범위를 재설정한다.

 

4. 반복문을 이용하여 입력 받은 강의들을 블루레이에 하나씩 넣어보며 사용된 블루레이의 개수를 확인한다.

+ 현재 탐색 중인 크기 mid값을 초과하면 다음 블루레이에 저장

 

4-1. 사용된 블루레이의 개수가 M이하라면 이전 res 값과 비교하여 갱신하고 더 작은 크기의 블루레이를 사용할 수 있는지 탐색한다. 

 

4-2. 사용된 블루레이의 개수가 M 초과라면 크기가 각 블루레이의 크기가 더 커야하므로, 더 큰 크기의 블루레이는 가능한지 탐색한다.

 

5. start가 end값보다 커지면 탐색을 종료한다.