[백준/Swift] 2512: 예산

안녕하세요

---

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

2512번: 예산

---

요즘 이분 탐색 문제를 풀고 있는데 자꾸 이분 탐색 범위의 최소나 최대를 제대로 파악하지 않아서 틀리네요...

하놔.. 더 집중해야겠어요

---

• 간단한 문제 해석부터 들어가겠습니다.

 

각 지역마다 예산을 요청 하는데, 국가예산의 총액은 미리 정해져 있습니다.

정해진 총액 이하 에서 가능한 한 최대의 예산을 각 지역에게 분배하는 것이 문제입니다!!

 

case : 

1. 지역의 요청 금액이 상한액( 이 액수를 우리가 이분 탐색을 통해서 정해야 합니다. )보다 작은 경우 지역의 요청 금액을 그대로 배정.

2. 지역의 요청 금액이 우리가 정한 상한액보다 높게 달라고하는 경우 가차없이 상한액만 지급

 

했을 때~ 각 지역에게 case에 따라 분배한 총액이 국가 예산보다 작거나 같은 경우일 때, 앞에서 구했던 각 지역에게 case에 따라 분배한 총액이 가능한 한 최대인 상한액을 구하는 것이 풀이 과정이 되겠습니다.

---

저는 이분 탐색을 통해 상한액을 구하는 방법으로 문제를 풀었습니다.

이때 상한액이 될 수 있는 범위 left , right 를 잘 정하셔야합니다.

 

각각 지역의 요청 예산을 받은 배열을 list라 가정한다면

left = list[0]으로 하면 잘못된 답이 나와서 문제를 틀리게 됩니다.

right는 list의 가장 큰 값으로 정했을 때

 

mid의 범위가 결정될 조건을 정해야 합니다.

(윗 글)각 지역에게 case에 따라 분배한 총액이 국가 예산 보다 작거나 같은 경우가 조건이 mid범위를 결정짓는 조건이 됩니다.

저는 requestBudget(list: target: budget: tempBudget: )함수를 통해 조건을 정했습니다.

---

다음은 코드입니다.

 

import Foundation
/**
 * result = 할당된 예산 값들이 최대값의 경우가 될 상한 액
 * left     = 상한액 될 수 있는 최소 금액
 * right   = 상한액 될 수 있는 최대 금액
 * requestBudget()을 만족시켰을 때 특정 상한액의 할당된 금액
 */
func binary_search(list : [Int], target : Int){
    
    var result       = 0
    var left         = 1
    var right        = list[list.count - 1]
    var assignBudget = 0
    
    while( left <= right){
        var tempBudget = 0
        let mid        = ( left + right )  / 2
        
        if requestBudget(list: list, target: target, budget: mid, tempBudget : &tempBudget) {
            //새로 구한 예산값들이 국가 예산과 가까운 값이라면 그 값과, 상한액을 저장!
            if tempBudget >= assignBudget{
                assignBudget = tempBudget
                result       = mid
                left         = mid + 1
            }
        }else{
            right = mid - 1
        }
        
    }
    
    print(result)
}
/**
 * 매개변수
 *  list       = 지역 별 요청 예산
 *  target  = 상한액
 *  budget = 국가 예산
 *  tempBudget = 지역별 예산의 합
 */
func requestBudget(list : [Int], target : Int, budget : Int, tempBudget : inout Int) -> Bool{
    var totalBudget = 0
    
    for i in 0..<list.count{
        totalBudget += list[i] - budget <= 0 ? list[i] : budget
    }
    
    if totalBudget <= target {
        tempBudget = totalBudget
        return true
    }else{
        return false
    }
}

func BOJ_2512(){
    
    var n        = Int(readLine()!)!
    var list     = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)
    var maxValue = Int(readLine()!)!
    
    binary_search(list: list, target: maxValue)
}

BOJ_2512()

긴 글 읽어주셔서 감사합니다.