[백준 1654] swift 랜선 자르기

문제 설명

 

문제 풀이

처음 접근법은 길이가 100이라고 가정하고 n개 이상의 랜선이 나오는지 체크,

100 -> 200 -> 300 늘려가며 생각하다 이진탐색을 떠올리게 되었다. (완전탐색보다 속도가 빠르기 때문에)

 

left는 1, right는 가진랜선의 최대길이로 두었다.

기본적인 이진탐색 풀이로 문제 해결!

 

 

코드

import Foundation

let input = readLine()!.split(separator: " ").map {Int(String($0))!}
let k = input[0], n = input[1]
var arrs = [Int]()
for _ in 0..<k {
    arrs.append(Int(readLine()!)!)
}

var left = 1
var right = arrs.max()!
var answer = 0
while left <= right {
    
    let mid = (left+right) / 2
    var sum = 0
    for arr in arrs {
        sum += arr/mid
    }

    if sum >= n {
        answer = mid // n개이상 랜선을 구할 수 있는 경우 answer에 저장
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(answer)