백준 2805번 나무 자르기

정답 :

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

let n = input[0]
let m = input[1]

let array = readLine()!.split(separator: " ").map{Int($0)!}.sorted()

var st = 0
var ed = array[n-1]

func solve(x : Int) -> Bool {
    var cur = 0
    for i in 0..<n {
        if array[i] > x {
            cur += array[i] - x
        }
        else {
            continue
        }
    }
    return cur >= m
}

while st < ed {
    var mid = (st + ed + 1) / 2
    if solve(x: mid) {
        st = mid
    } else {
        ed = mid - 1
    }
}
print(st)

해당 문제는 전선 자르기 문제와 비슷하다.

 

하지만, st를 1이 아닌 0으로 설정해야 정답이 되었다.  1로 설정했을 경우, 반례가 나타나는 듯 하다.