문제 설명
보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.
한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.
상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.
상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 10^9, 1 ≤ M ≤ 300,000, M ≤ N)
다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.
출력
첫째 줄에 질투심의 최솟값을 출력한다.
문제 풀이
- 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이므로 각 학생에게 보석을 질투심 이하로 나누어 주어야 한다.
- 이를 이용해서 Left는 1, Right는 가장 많은 보석의 개수로 두고 이분 탐색을 한다.
- 중간값으로 보석을 나눠준다고 가정할 때 보석을 받아야 하는 학생의 수가 실제 학생의 수보다 작아야 보석을 나눠줄 수 있다.
- 보석을 나눠줄 수 있는 경우 중 최솟값을 찾는다.
소스 코드
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int arr[] = new int[M];
int left = 1, right = 0, mid = 0, sum, answer = 0;
// 각 색상별 보석의 개수
for (int i = 0; i < M; i++) {
arr[i] = Integer.parseInt(in.readLine());
right = Math.max(right, arr[i]);
}
// 이분 탐색 하면서 최솟값 찾기
while (left <= right) {
// 질투심이 mid가 되도록 보석 나눠주기
mid = (left + right) / 2;
sum = 0;
for (int i = 0; i < M; i++) {
sum += arr[i] / mid;
if (arr[i] % mid != 0) {
sum++;
}
}
// 보석을 나눠줄 수 없는 경우
if (sum > N) {
left = mid + 1;
}
// 보석을 나눠줄 수 있는 경우
else {
right = mid - 1;
answer = mid;
}
}
// 질투심의 최솟값 출력
System.out.println(answer);
}느낀 점
아직도 이분 탐색이 어려워서 한참 헤맸던 문제. 스터디원이 힌트를 줘서 겨우 풀긴 풀었는데, 그냥 넘어가기에는 스스로 이해가 안 가서 다시 고민하고 이분 탐색도 더 찾아본 뒤 다시 풀었다. 그리고 잊지 않으려고 오랜만에 블로그에도 올리기!
문제 고를 때는 Silver 3 이니까 꽤나 만만하게(?) 보고 어렵지 않게 풀 수 있겠지 싶었는데 막상 풀기 시작하니까 이분 탐색을 어떻게 적용할 지 감이 안 잡혀서 어려웠다🥲 그래도 여러 번 들여다보고 고민하니까 이젠 풀이도 이해가 가고 다음에 이분 탐색이 나오면 지금보다는 쉽게 풀 수 있을 것 같다.
물론 내가 이해한 내용을 글로 적는 건 어려워서 내 풀이를 보고 다른 사람들이 이해할 수 있을 지는 모르겠지만^^... (혹시 이해가 안 가시는 분들 댓글로 질문이나 피드백 대환영입니다) 그래도 정리를 하긴 했다는 것에 만족! 까먹지 말자💪
