[백준(BOJ)] 2792 보석 상자 - 스위프트 (Swift)

[Silver I] 보석 상자 - 2792

문제 링크

성능 요약

메모리: 75352 KB, 시간: 204 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2024년 1월 15일 16:08:28

문제 설명

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

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

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

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

입력

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

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

출력

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

 

풀이

우선 구해야 하는 값은 질투심이기 때문에, 해당 값을 기준으로 이분 탐색을 진행해야겠다고 생각했습니다.

보석의 개수를 기준으로 줄 수 있는 사람의 수를 계산해줍니다.

다음과 같은 예시가 있다고 생각해봅시다.

5 2
7
4

만약 보석을 4개씩 나눠준다면, 4 / 3 / 4 개로 총 3명의 아이가 보석을 받을 수 있습니다.

하지만 이렇게 된다면 받지 못하는 아이가 생겼고, 이는 질투심이 최소가 아님을 의미합니다.

 

따라서 보석을 나눠주었을 때 받을 수 있는 아이의 수와 최대로 줄 수 있는 아이의 수를 비교하여,
더 많은 아이들이 받을 수 있다면 보석의 개수를 줄여 질투심을 줄이고, 받을 수 있는 아이의 수를 초과했다면 보석의 개수를 늘리는 방식으로 해결하였습니다.

 

다음은 코드입니다.

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var jews = [Int]()

for _ in 0..<m {
    let input = Int(readLine()!)!
    jews.append(input)
}

var (left, right) = (1, jews.max()!)

while left <= right {
    let mid = (left + right) / 2
    var total = 0

    for jew in jews {
        if jew % mid == 0 {
            total += jew / mid
        } else {
            total += (jew / mid) + 1
        }
    }

    if total > n {  // 받을 수 있는 학생 수를 초과했으므로 인당 받는 보석개수(mid)를 늘려줌
        left = mid + 1
    } else {    //  못받은 학생에게 나눠주어 인당 받는 보석개수(mid)를 줄여줌
        right = mid - 1
    }
}
print(left)