[백준] (Swift) 2512번 - 예산 (이분탐색, 파라메트릭 서치)

 

⚫️ 문제

https://www.acmicpc.net/problem/2512

2512번: 예산

 

⚫️ 나의 풀이

보자마자 이코테 책에 있는 '파라메트릭 서치' 문제의 대표유형인듯 싶다. 어려운 문제는 아니지만, 풀이를 하다가 한가지 놓치고 생각한 부분이 있어서 기록하고자 블로그 글을 작성한다.

◾️ 놓치고 생각한 부분

처음에 생각했을 때, start는 주어진 지방예산의 최소값, end 는 주어진 지방예산의 최대값으로 설정하면 되겟구나 싶어서 그렇게 구현했다. 근데, 이렇게 하니까 계속 틀리는 것이다! 이유가 뭘까

조건에서 최소 한개의 지방예산은 무조건 충족해야한다라는 조건이 없지 않은가? 그렇다. 그래서 start값을 0부터 시작하는게 맞다. 백준 예제에서는 국가 총예산을 지방예산들보다 크게 주어졌지만, 조건을 잘보면 국가 총에산은 한자릿수 일 수도 있다.  (지방 갯수보다 크다는 조건이기 때문에 4개의 지방이 주어졌다면, 국가총예산은 4일수도있다는 것!)

그렇기 때문에 start를 0부터 시작해야했다. 

⚫️ 정답코드

import Foundation

let n = Int(readLine()!)!
let cities = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)
let budget = Int(readLine()!)!

func binarySerach(arr: [Int], start: Int, end: Int) -> Int {
    var start = start
    var end = end

    while start <= end {
        let mid = start + ((end - start) / 2)
        let total = sum(cities: cities, mid: mid)

        if budget >= total {
            start = mid + 1

        } else if budget < total {
            end = mid - 1
        }
    }

    return end
}

func sum(cities: [Int], mid: Int) -> Int {
    var total = 0
    for i in 0..<n {
        if mid > cities[i] {
            total += cities[i]
        } else {
            total += mid
        }
    }

    return total
}

print(binarySerach(arr: cities, start: 0, end: cities.max()!))