[Swift 알고리즘] 백준 2512 예산

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

어제 bfs랑 싸우다가 너무 힘들어서... 탐색에서 도망쳤습니다(도망친곳이 이분 '탐색'ㅋㅋㅋㅋ)

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

import Foundation
// 백준 2512 예산 이분탐색 실3

let n = Int(readLine()!)!
let arr: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = Int(readLine()!)!

var answer = 0

// idea: 제일 큰 수에서 부터 이분탐색으로 찾기

func binarySearch(l: Int, r: Int) {
    let mid = (l + r) / 2
    if mid == l || mid == r { // left가 Mid랑 같아짐 -> 탐색 종료
        return
    }
    var total = 0
    for a in arr {
        if a > mid { total += mid }
        else { total += a }
    }
//    print("total", total, "l, mid, r", l, mid, r)
    
    if total > m { // 상한이 너무 높음
        binarySearch(l: l, r: mid)
    } else {
        answer = max(answer, mid)
        binarySearch(l: mid, r: r)
    }
}

if arr.reduce(0, +) <= m {
    answer = arr.max()!
} else {
    binarySearch(l: 0, r: arr.max()!)
}

print(answer)

아이디어는 간단합니다. 최고 요청 금액과 0원 사이에서 binary search를 해주면 됩니다!

참고로 min == r에 대한 조건은 빼도 되는데 실수로 들어갔답니다. 머-쓱

(처음에 0~max로 했다가 뭐에 홀려서 min~max로 했다가 틀린 어이없는 일이...)