[2023-05-11] 2512 예산 (Kotlin) + 12 문제

 

 

문제 링크: https://www.acmicpc.net/problem/2512

2512번: 예산

 

첫 번째 시도 (틀렸습니다.)

 

// ex) 120, 110, 150, 140
// 국가 예산: 485
// 1. 정렬 110, 120, 140, 150
// 2. 국가 예산 개수로 나누기 : 121
// 3. 각 지방 예산이 121보다 낮을 경우, 그 차이를 더해주기
// (121 - 110) + (121 - 120) = 12
// 4. 121보다 큰 지방 예산의 개수로 나눠주기: 12 / 2 = 6
// 5. 답: 121 + 6 = 127


package fourtyfirst
import java.io.*
import java.math.BigInteger

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = br.readLine().split(' ').map{it.toInt()}.sorted()
    val price = br.readLine().toInt()
    var sum = list.sum()
    
    // 총 더한 금액이 국가 예산보다 작거나 같을 때
    if (price >= sum){
    // 최대값 출력
        println(list.max())
    }
    else{
    
        val a = price / n
        var s = 0
        var max = 0
        for (index in list.indices){
            if (list[index] <= a)
                s += a - list[index]
            if (list[index] > a){
                val diff = list.size - index
                if (s % 2 == 0)
                    max = a + s / diff
                else
                    max = a + s / diff + 1
                break
            }
        }
        println(max)
    }
}

 

그냥 논리가 틀렸습니다.

 

유형을 봤고, 이분 탐색으로 풀었습니다.

 

 

두 번째 시도 (맞았습니다.)

 

package fourtyfirst
import java.io.*
import java.math.BigInteger

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = br.readLine().split(' ').map{it.toInt()}
    val price = br.readLine().toInt()

    var start = 0
    var end = list.max()
    if (list.sum() <= price)
        println(list.max())
    else{
        while (start <= end){
            val mid = (end + start) / 2
            var totalBudget = price
            for (index in list.indices){
                if (list[index] > mid)
                    totalBudget -= mid
                else
                    totalBudget -= list[index]
            }
            if (totalBudget >= 0){
                start = mid + 1
            }
            else
                end = mid - 1

        }
        println(end)
    }

}