[Python] 2343 - 기타 레슨

1. 문제 정의

M개의 블루레이의 용량이 최소가 되도록 주어진 영상의 길이를 차례대로 담아야 한다. 그리고 그때의 최소가 되는 블루레이의 크기를 구하는 문제이다.

 

2. 풀이 방식

매개변수의 활용 및 이분 탐색을 활용하여 문제를 해결해야 한다.

 

우리가 구해야 할 값은 M개의 블루레이가 같은 크기로 최소가 되도록 하는 값이다. 

그 값을 우리는 매개변수를 활용하여 설정해준 뒤, 입력으로 주어진 영상의 길이를 차례차례 더할 것이다.

 

그 값과 mid 값을 비교하며 이분 탐색을 이어간다.

비교 값의 결과에 따라 블루레이의 개수를 하나 씩 늘려간다.

 

블루레이의 개수가 주어진 M개를 만족하더라도 길이를 더욱 최소화 할 수 있을것이다. 그렇기에 조건에서 블루레이의 개수와 M이 같을때에도 이분 탐색을 진행하도록 설정한다.

# 2343 기타 레슨

import sys

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

start, end = max(li), sum(li) # 시작값 : 가장 큰 용량, 끝값 : 모든 용량의 합

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

    blueray = 1 # 블루레이 개수
    sum_size = 0 # 하나의 블루레이 안에 담기는 용량의 크기

    for ix in li:
        if ((sum_size + ix) <= mid): # mid보다 작거나 같은 경우(한 블루레이 안에 들어갈 수 있는 최대 용량 만큼 넣은 경우)
            sum_size += ix
        else: # 아닌 경우 -> 블루레이 개수 증가, 두 번째 블루레이에 용량을 더함
            blueray += 1
            sum_size = ix
    
    if (blueray <= M): # 블루레이 개수가 M개를 넘기 직전까지 용량을 줄여야 함
        end = mid - 1
    else:
        start = mid + 1

print(start)

 

3. 후기

이분 탐색에서 탐색 대상을 잘 설정하는 것이 중요하다 생각이 든 문제였다. 또한 매개 변수를 잘 설정하여 코드의 이해를 더욱 도울 수 있겠다는 생각을 하였다.