백준 15810 풍선 공장

출처: www.acmicpc.net/problem/15810

분류: 이분탐색

---

접근방식

스태프 한 명이 만들 수 있는 풍선의 개수는 시간 / 걸리는 시간 으로 구해줄 수가 있고
특정 시간에 만들어진 풍선의 개수는 해당 시간에 각 스태프가 만들 수 있는 풍선의 개수를 모두 더해 구할 수 있습니다.

이제 최대 걸리는 시간을 특정할 수 있다면 각 시간에 원하는 풍선 개수를 넘거나 같은 시간을 찾아 이분 탐색으로 반씩 잘라가며 찾을 수 있습니다.

처음으로 풍선의 개수를 넘거나 같은 시간을 찾아야 하기 때문에 이분탐색 lower bounded 로 풀어줬습니다.

마지막으로 최대 걸리는 시간(High)을 정해줘야 합니다.

처음에는 staff의 최대 범위가 1000000이여서 적당히 원하는 풍선의 개수 * 1000000 정도로 해줘서 통과하긴 했는데,

보다 정확히는 최악의 경우 만드는 시간이 가장 적게 걸리는 스테프 혼자서 모든 풍선을 만들 때로 생각해서 풍선의 개수 * 만드는 데 가장 적게 걸리는 스테프의 시간 특정해줄 수 있습니다.

 

해결방법

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let staff = readLine()!.split(separator: " ").map { Int(String($0))! }

var low = 0
var high = nm[1] * staff.min()!

func numberOfBalloon(at time: Int) -> Int {
    staff.reduce(0, { $0 + time / $1 })
}

while low < high {
    let mid = (low + high)/2
    if nm[1] <= numberOfBalloon(at: mid) {
        high = mid
    } else {
        low = mid + 1
    }
}

print(low)

배운점

이분 탐색인 걸 알고 접근했는데도 접근하기가 쉽지 않았다. 이분 탐색은 구현 자체는 괜찮은데 접근이 참 어려운 것 같다. 최대한 많은 문제를 접하고 익숙해지자 !!!!