백준 2343 기타 레슨 Python3

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

2343번: 기타 레슨

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2343.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_bluelay_size(M, lectures):
    left = 0
    right = sum(lectures)
    answer = right
    while left <= right:
        mid = (left+right)//2
        bluelay = [0]*M
        i = 0
        for lec in lectures:
            if lec + bluelay[i] <= mid:
                bluelay[i] += lec
            else:
                i += 1
                # 블루레이에 다 못 담는 경우
                if i == M or lec > mid: break
                bluelay[i] += lec
        else:
            answer = min(answer, mid)
            right = mid-1
            continue
        left = mid+1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
lectures = list(map(int, input().split()))
print(get_bluelay_size(M, lectures))

---

풀이 과정

풀이 시간 31분

모두 같은 크기의 M개의 블루레이에 N개의 강의를 순서대로 모두 녹화할 때 가능한 블루레이의 크기 중 최소를 구하는 문제이다.

따라서 블루레이 크기에 대해 이분 탐색을 적용할 수 있다.

import sys
def get_bluelay_size(M, lectures):
	#이분 탐색 범위 초기화, 블루레이 크기는 0분에서 강의의 전체 길이 사이이다
    left = 0
    right = sum(lectures)
    answer = right
    
    #이분 탐색
    while left <= right:
    	#블루레이 크기를 mid로 가정
        mid = (left+right)//2
        #크기가 mid인 M개의 블루레이에 녹화된 강의의 길이를 나타내는 배열
        bluelay = [0]*M
        #강의가 들어갈 블루레이의 인덱스
        i = 0
        
        for lec in lectures:
        	#현재 강의를 i번째 블루레이에 녹화할 수 있는 경우
            if lec + bluelay[i] <= mid:
            	#i번째 블루레이에 강의를 녹화한다
                bluelay[i] += lec
                
            #현재 강의를 i번째 블루레이에 녹화할 수 없는 경우
            else:
            	#블루레이 인덱스 카운팅
                i += 1
                #블루레이가 부족하거나, 현재 강의의 크기가 블루레이의 크기보다 큰 경우 -> 블루레이의 크기가 mid보다 커야한다
                if i == M or lec > mid: break
             	#i번째 블루레이에 강의를 녹화한다
                bluelay[i] += lec
                
        #모든 강의를 M개의 블루레이에 녹화할 수 있는 경우,
        else:
        	#answer값 갱신
            answer = min(answer, mid)
            #가능한 블루레이의 최소 크기를 구하기 위해 right 범위를 줄인다
            right = mid-1
            continue
        
        #모든 강의를 M개의 블루레이에 녹화할 수 없는 경우, left 범위를 늘려 더 큰 블루레이 크기로 탐색한다
        left = mid+1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
lectures = list(map(int, input().split()))
print(get_bluelay_size(M, lectures))

#시간복잡도 = O(log n), 공간복잡도 = O(n)