[백준/BOJ] 2792번: 보석 상자

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

2792번: 보석 상자

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, 109]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

출력

첫째 줄에 질투심의 최솟값을 출력한다.

해설

이분 탐색을 이용하여 문제를 풀어야 한다.

문제에서의 핵심을 보면,

• 보석을 받지 못하는 학생이 있어도 된다.
• 학생은 항상 같은 색상의 보석만 가져간다.
• 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다.

이분 탐색을 위해 low, high변수를 선언해주자.

low는 1이고, high은 보석이 더 많은 색상의 개수라 하자.

mid는 한 사람 당 가져가는 보석의 수가 된다.

 

이제 보석을 가져갈 인원수를 구해야 한다.

한 사람 당 가져갈 보석의 수를 구했으니 (각 색상 별 보석의 개수 / 한 사람 당 가져가는 보석의 개수)를 하면 된다.

나눴을 때 0으로 나눠떨어지지 않는다면 누군가는 더 가져가야 하는 것이므로 +1을 해준다.

 

이제 보석을 가져갈 인원이 총 학생의 수보다 많은지 적은지를 비교해보자.

보석을 가져갈 인원이 총 학생의 수보다 크다면 더 적은 학생이 더 많은 보석을 가져갈 수 있는 것이다.

이 말은 질투심을 더 높여야 한다는 것이다.

따라서 low를 mid + 1로 바꿔준다.

 

보석을 가져갈 인원이 총 학생의 수보다 같거나 작다면 값을 저장해둔 후, 질투심을 더 낮출 수 있는지 봐야한다.

따라서 high을 mid -1로 바꾼다.

소스 코드

lateinit var jewelNum: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    var max = 0
    jewelNum = IntArray(m)
    repeat(m) { i ->
        jewelNum[i] = readLine().toInt()
        if(max < jewelNum[i]) max = jewelNum[i]
    }
    println(binarySearch(n, max))
}

fun binarySearch(n: Int, right: Int): Int {
    var min = Integer.MAX_VALUE
    var low = 1
    var high = right
    while(low <= high) {
        val mid = (low + high) / 2
        var sum = 0
        for(i in jewelNum) {
            val people = if(i % mid == 0) i / mid else i / mid + 1
            sum += people
        }
        if(n >= sum) {
            min = Math.min(min, mid)
            high = mid - 1
        }
        else low = mid + 1
    }
    return min
}