2343번: 기타 레슨

문제 풀이 아이디어

특정 범위 내에서 최적화된 값을 찾는 문제입니다. 이런 문제는 이진탐색을 활용한 파라메트릭 서치를 사용해서 풀 수 있습니다.

특정 값이 조건에 만족하는지 알 수 있는 함수를 구현한 뒤 이진탐색과 이 함수를 활용해서 최적화된 값을 찾아내면 됩니다.

코드

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

// 어떤 size의 블루레이에 대해서 몇장의 블루레이가 필요한지 계산
func cntBR(size: Int) -> Int {
    var current = size
    var cnt = 1
    
    for lecture in lectures {
        if current < lecture {
            cnt += 1
            current = size
        }
        current -= lecture
    }
    
    return cnt
}

// 초기값
var start = lectures.max()!
    //👉 적어도 가장 큰 강의 1개는 담을 수 있어야 함
var end = lectures.reduce(0, +)
    //👉 한 블루레이에 모든 강의를 담을 수 있는 경우
var ans = 0

// 이진탐색 구현
while start <= end {
    let mid = (start + end) / 2
    
    if cntBR(size: mid) <= M {
        end = mid - 1
        ans = mid
    } else {
        start = mid + 1
    }
}

print(ans)