[Swift 백준] 2512 예산

 

풀이 아이디어

이분탐색 문제입니다.

이분탐색에선 최소 최댓값의 기준을 잡는 것이 중요합니다.

해당 문제에서 1번 조건으로 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다 했으므로

최댓값은 input의 max값이 됩니다.

 

나머지는 일반적인 이분탐색이고, 핵심부분에 주석으로 설명을 덧붙였습니다

풀이

import Foundation

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

var left = 0
var right = input.max()!
var result = 0

while left <= right {
    let mid = (left + right) / 2
    
    // 현재 상한액(mid)로 배정한 예산의 총합 계산합니다
    // min($0, mid)를 통해, 만약 mid가 내 상환액보다 크다면 내 상환액을 택합니다.
    let allocated = input.map { min($0, mid) }.reduce(0, +)
    
    if allocated <= total {
        result = mid
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(result)