백준 1654번 랜선 자르기

정답 :

let input = readLine()!.split(separator: " ").map{Int($0)!}
let k = input[0]
let n = input[1]
var st = 1
var ed = 0x7fffffff
var array = [Int]()
for _ in 0..<k {
    let line = Int(readLine()!)!
    array.append(line)
}

func solve(x : Int) -> Bool {
    var cur = 0
    for i in 0..<k {
        cur += array[i] / x
    }
    return cur>=n
}
while st < ed {
    var mid = (st + ed + 1) / 2
    if solve(x: mid) {
        st = mid
    } else {
        ed = mid - 1
    }
}

print(st)

해당 문제는 위의 그래프를 전적으로 이용한다.

 

개수에 가장 가까운 수를 찾으면 되는 부분이다. 따라서 우리는 st를 1로 ed 를 최대의 정수로 진행하여 그 중간값을 대입하여 N개의 개수가 나오는지 확인하면 된다.