이번 문제는 백준의 실버 1 문제 보석 상자 문제이다.
차근차근 문제를 읽어보도록 하자.
선생님이 최대 10^9명의 아이들에게 보석을 나누어 주려고 한다.
보석은 여러 색으로 구성되어 있는데, 최대 300,000가지의 색상이 가능하다.
이 때, 각 학생들은 동일한 색의 보석만 들고갈 수 있다.
가장 많이 가져가는 학생이 최소로 보석을 들고 가는 경우는 어떻게 될까?
문제 분석
우선 아이들의 수가 굉장히 많은 것을 눈여겨 봐야한다.
아이들의 최대 수가 무려 10억이나 된다.
이는 int의 최대 값을 넘어가는 값으로, 매우 큰 값이다.
즉 배열을 만들거나 해서 직접 동작을 구현하는 문제는 아니라는 말이 된다.
보통 이렇게 매우 큰 값에 대해서 탐색을 진행할 때는 이분탐색을 사용한다.
보통 Parametric search라고 하며 최소, 최대 값 탐색에 있어 유용하다.
이분 탐색
과연 어떤 Parameter를 기준으로 이분 탐색을 진행해야 할까?
보통은 매우 큰 수를 기준으로 이분 탐색을 진행하게 되는데,
그럼 학생들의 수를 줄였다 늘였다 하며 탐색을 진행해야 할까?
그건 아니라고 생각한다.
왜냐하면 학생들의 수는 고정되어 있는 값으로 주어지기 때문이다.
우리가 판단해야 할 부분은, 초콜릿을 최대한 많이 분포시키는 것이다.
만약 학생의 수가 작았다면 Greedy하게 풀 수 있었을 것이다.
내 생각에는 가장 많이 받는 초콜릿의 값을 기준으로 하는게 좋을 것 같다.
즉, 어차피 답으로 구해야 하는 질투심의 값을 기준으로 하는 것이다.
질투심을 기준으로 특정 색상을 나누면, 해당 색을 받을 수 있는 학생의 수가 나온다.
이 때 최종적으로 받을 수 있는 모든 학생의 수가 주어진 학생의 수보다 많다면?
우리는 질투심을 더 높게 설정할 수 있게 되는 것이다.
반대로 최종적으로 받을 수 있는 모든 학생의 수가 주어진 학생 수보다 적다면?
우리는 질투심을 더 낮추어 분포도를 높일 필요가 있다.
위의 논리대로 코드를 구현해보도록 하자!
while (left_v <= right_v) {
int mid = (left_v + right_v) / 2;
int kids = 0;
for (int i = 0; i < colors; i++) {
kids += (color_jewels[i] / mid);
// mid 값이 질투심이라면, 보석 / mid 명이 받을 수 있다.
if (color_jewels[i] % mid != 0)
kids++;
// 나머지가 0이 아니라면 한명 더 받을 수 있다.
}
if (kids <= num) {
right_v = mid - 1;
answer = mid;
}
else
left_v = mid + 1;
}이분 탐색을 진행할 때, 가장 많은 보석이 있는 색상을 기준으로 잡는다.
해당 값에서부터 질투심 값을 조정하며 최소값을 찾는 것이다.
모든 보석 수를 돌며 질투심 값으로 나누었을 때 받을 수 있는 학생 수를 구한다.
나누었는데 나머지가 남는다면, 1명의 학생이 나머지를 받을 수 있는 것이다.
계산된 학생 수가 주어진 학생 수보다 많다면, 질투심을 높일 수 있다.
반대로 학생 수보다 적다면, 질투심을 낮추어야 한다.
이 때 왜 right를 올릴 때 답을 갱신해야 하는 것일까?
만약 학생 수에 대해서 모자랄 때 갱신을 한다고 생각해보자.
그럼 못받는 학생이 생긴다는 말이 되는데, 내가 계산한 방식을 다시 생각해보자.
질투심만큼 동일하게 모든 학생에게 나누고, 남은 것을 남는 학생에게 주었다.
그래도 모든 학생에게 나누어 줄 수 없다면, 사실 다른 학생이 나누어줘도 무방하다.
왜냐하면 질투심만큼 가진 학생은 최소한 1명만 있으면 되기 때문이다!
결국 어차피 모든 학생에게 나누어 줄 수 있게 되는 것이다.
그리고 우리는 최대한 질투심을 낮추는 것이 목적이다.
즉, 분포도를 가장 고르게 만들어야 하는 것이다.
따라서 우리는 학생 수와 계산된 학생 수가 같거나 클 때 정답을 갱신해야 한다!