[이분 탐색] 백준 실버3 2512번: 예산(Swift)

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

2512번: 예산

Code

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

var sum = 0

list.forEach {
  sum += $0
}

if sum <= total {
  print(list.max()!)
} else {
  var right = list[list.count - 1]
  var left = 1
  var result = 0
  
  while true {
    let med = (right + left) / 2
    var totalBudget = 0
    
    list.forEach {
      totalBudget += $0 <= med ? $0 : med
    }
    
    if totalBudget < total {
      left = med
      result = med
    } else if totalBudget > total {
      right = med
    } else {
      result = med
      break
    }
    
    if med + 1 == right {
      break
    }
  }
  print(result)
}

풀이과정

먼저, 문제를 정리해보면 

지방 요청 예산이 리스트로 주어지고, 총 국가예산이 주어진다.

지방 요청 예산의 합이 총 국가예산보다 작으면, 요청 예산대로 예산을 배분해주면 된다.

즉 출력값은 리스트의 최대값이 된다.

하지만, 요청 예산의 합이 국가예산보다 크다면, 상한액을 정해 요청 예산이 상한액보다 작은 지방은 요청대로 예산을 배정하고,

큰 지방은 상한액으로 예산을 배정한다.

때문에, 상한액을 이분 탐색을 통해 계산한다.

때문에 left엔 1을 right엔 list의 최대값을 담아 중간값(med)을 계산한다.

중간값을 이용하여 요청 예산이 중간값보다 작거나 같다면, 요청예산 그대로 아니라면 중간값을 더해 총 합을 계산한다.

해당 총합이 주어진 국가예산보다 크다면 right에 med를 담는다.

작으면 left에 med를 담고, result엔 상한액이 될 수 도 있는 med를 담아준다.

둘이 같다면, 더 이상 계산할 필요가 없으므로 result에 med값을 담고 반복분을 break 해준다.