[Swift 알고리즘] 백준 1654 랜선 자르기

안녕하세요 코코종입니다.

오늘도 이분탐색! 이제 이분탐색에 좀 익숙해진 것 같네요 허헣

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/29.
//

import Foundation
// 1654 랜선 자르기 이분탐색 실2

let kn = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = kn[0]
let n = kn[1] // 만들려는 수

var arr: [Int] = []
for _ in 0..<k {
    arr.append(Int(readLine()!)!)
}
let maxV = arr.max()!

var answer = 0
// N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오
var l = 1
var r = maxV

func binarySearch() {
    while l <= r {
        let mid = (l+r) / 2
        var cnt = 0
        
        for a in arr {
            cnt += a/mid // mid길이로 만들수 있는 개수
        }
        
        if cnt >= n {
            l = mid + 1
            answer = max(answer, mid)
        } else { // n보다 적은 갯수 -> mid를 줄여야함
            r = mid - 1
        }
    }
    
    print(answer)
}

binarySearch()

참고로 입력 범위에서 '랜선의 길이는 231-1보다 작거나 같은 자연수이다.' 라고 했으니 혹여나 최대 길이를 Int.max로 하면 mid를 구할때 1+max가 되어버려서 overflow가 납니다. 또한 N개보다 많이 만들어도 된다고 했으니(이게 아마 이전에 이해가 안가던 공유기에 대한 해답이 아닐까 싶네요..) cnt >= n 일때도 answer에 포함시킵니다.