2512번: 예산

문제 풀이 아이디어

• 완전탐색을 해도 답을 구할 수 있습니다.
  • 시간복잡도: O(n)
• 하지만 이진탐색을 활용하면 더 빠르게 구할 수 있습니다.
  • 시간복잡도: O(logn)
• 이진탐색을 활용해서 조건에 만족하는 최댓값 (혹은 최솟값)을 찾는 것을 파라메트릭 서치라고 합니다.
  • 어떤 예산이 “총 예산 조건"을 만족하는 "최댓값"인지 구하면 됩니다.

코드

// 입력 받기
let N = Int(readLine()!)!
let requests = readLine()!.split(separator: " ").map { Int(String($0))! }
let limit = Int(readLine()!)!

// 파라메트릭 서치 구현
func parametricSearch() -> Int {
    var start = 0
    var end = requests.max()! //👉 상한선은 예산요청 중에 가장 높은 값
    var mid = (start + end) / 2 //⭐️ 반복문 밖에서 return 해야 하므로 반복문 scope외에 mid 선언
    
    while start <= end {
        let totalBudget = requests.reduce(0) { $0 + ($1 < mid ? $1 : mid) }
            //👉 reduce문 활용 (mid 보다 작으면 예산 모두 주고 mid 보다 크면 mid 만큼만)
        if totalBudget > limit { //👉 limit보다 크면 mid보다 아래에서 search (조건 만족 위해)
            end = mid - 1
        } else { //👉 limit보다 작으면 mid보다 위에서 search (최댓값을 찾기 위해)
            start = mid + 1
        }
        mid = (start + end) / 2
    }
    
    return mid
}

print(parametricSearch())