백준 2343: 기타 레슨(python)

문제

---

풀이

 

이진 탐색을 사용해 풀이하는 문제다. 파이썬의 bisect 라이브러리를 사용해 별도의 구현 없이 풀이할 수 있다.

 

이때 주의해야 하는 것은 블루레이 녹화 시 강의의 순서가 바뀌어서는 안 된다는 점인데, 초기 입력값을 정렬할 수 없으므로 이진 탐색을 수행하기 위해서는 배열이 먼저 정렬되어야 한다는 조건을 만족할 수 없다.

 

이진 탐색 문제로 분류되는 것을 보면 어떤 식으로든 정렬된 배열을 다루어야 할 것이므로, 관점을 바꾸어 입력된 배열이 아닌 입력값의 부분합 배열 sum[]을 이진 탐색에 사용할 수 있다. sum[i] = arr[0:i]인 sum은 항상 오름차순 정렬된 배열이므로 이진 탐색이 가능하다.

문제를 풀이할 때 부분합 배열 sum[]을 직접 생성해 사용하지는 않지만, 전반적인 아이디어는 이 점에 기반한다.

 

각 강의 길이들을 lectures[] 배열에 저장하였으며, 이진 탐색을 진행할 범위의 양 끝 인덱스 low, high와 현재 사용한 블루레이 개수를 저장할 count, 현재 블루레이에 담긴 강의들의 길이 합을 저장할 current 변수를 사용한다.

low = max(lectures)
high = sum(lectures)

블루레이의 크기는 가장 긴 강의의 길이 이상, 강의 길이의 총합 이하이므로 low와 high를 위와 같이 초기화한다.

이 경우 mid=(low + high)/2는 블루레이 하나의 크기이며, 이진 탐색을 수행해 전체 강의를 mid 크기로 나눠 담을 수 있는지 판단한다.

while low < high:   #이진 탐색
	mid = (low + high) // 2

	if divide((mid)):   #전체 강의를 mid 크기로 나눠 담을 수 있으면
		high = mid  #더 잘게 나눠도 되므로 mid를 감소시켜 최적의 경우 탐색
	else:   #현재 mid의 크기로는 M개의 블루레이에 나눠 담을 수 없으면
		low = mid+1 #mid를 증가시켜 더 크게 나눔으로써 M 감소
return low  #low에 최소 블루레이 크기 저장

 

이때 사용한 divide() 함수는 아래와 같다.

count = 1
current = 0

 현재 블루레이의 개수를 저장할 count 변수와 현재 블루레이에 담긴 강의들의 길이 합을 저장할 current 변수를 선언하고,

count와 current를 증가시키며 조건에 부합하는 블루레이의 길이와 개수를 탐색한다.

def divide(size):   #블루레이의 크기가 size일 때 강의를 M개 이하의 블루레이에 나눠담을 수 있는지
	count = 1   #블루레이 개수
	current = 0 #현재 블루레이에 담긴 강의들의 길이 합

	for i in lectures:
		if current + i > size:  #현재 블루레이에 강의를 더 담을 수 없음
			count += 1  		#블루레이 개수 증가
			current = i 		#새로운 블루레이에 강의 담음
		else:  				#현재 블루레이에 강의를 담을 수 있으면
			current += i    #현재 블루레이에 담음
		
        if count > M:   	#블루레이 개수가 M보다 크면
		return False    #현재 size는 실패
	return True #M개 이하의 블루레이에 나눠 담을 수 있으면 현재 size는 성공

---

전체 코드

import sys
input = sys.stdin.readline

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

def minimum(N, M, lectures):
    low = max(lectures)
    high = sum(lectures)

    def divide(size):
        count = 1
        current = 0

        for i in lectures:
            if current + i > size:
                count += 1
                current = i
            else:
                current += i
            if count > M:
                return False 
        return True

    while low < high:
        mid = (low + high) // 2

        if divide((mid)):
            high = mid
        else:
            low = mid+1
    return low

print(minimum(N, M, lectures))