백준 - 기타 레슨 (2343)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])
let lectures = readLine()!.split(separator: " ").map{ Int(String($0))! }

var start = lectures.max()!
var end = lectures.reduce(0, +)

while start <= end {
    let mid = (start + end) / 2
    var count = 0
    var sum = 0
    
    for lecture in lectures {
        if sum + lecture > mid {
            count += 1
            sum = 0
        }
        sum += lecture
    }
		count += 1
    if count > M {
        start = mid + 1
    } else {
        end = mid - 1
    }
}

print(start)

• 이진탐색을 활용하여 가능한 블루레이 크기 중 최소를 찾는다.
• 필요한 블루레이 개수가 M보다 크다는 것은 M개의 블루레이로 모든 강의를 담을 수 없다는 뜻이기 때문에 블루레이의 크기를 늘려주어야 한다.
  • M보다 작을 때는 블루레이의 크기가 충분하기 때문에 블루레이의 크기를 줄여도 된다는 뜻이다.