알고리즘
[Java] 백준 2792번 보석 상자
J3SUNG
2023. 8. 23. 01:53
728x90
이분탐색 문제입니다.
모든 보석을 나누어 줄 때 최소 질투심의 값을 구해야합니다.
질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수입니다.
보석의 개수로 이분탐색을 진행하고 보석이 해당 개수로 나누어 떨어지지 않으면 1을 추가합니다.
for (int i = 0; i < m; ++i) {
cnt += arr[i] / mid;
if (arr[i] % mid != 0) {
++cnt;
}
}
위의 과정을 반복하여 최종적으로 left의 값을 출력해주었습니다.
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int n;
static int m;
static int[] arr;
static int result;
public static void main(String[] args) throws Exception {
simulation();
}
public static void init() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[m];
for (int i = 0; i < m; ++i) {
arr[i] = Integer.parseInt(br.readLine());
}
}
public static void printResult() throws Exception {
bw.write(result + "");
bw.close();
}
public static void binarySearch() throws Exception {
int left = 1;
int right = 1_000_000_000;
while (left <= right) {
int mid = (left + right) / 2;
int cnt = 0;
for (int i = 0; i < m; ++i) {
cnt += arr[i] / mid;
if (arr[i] % mid != 0) {
++cnt;
}
}
if (cnt <= n) {
right = mid - 1;
} else {
left = mid + 1;
}
}
result = left;
}
public static void simulation() throws Exception {
init();
binarySearch();
printResult();
}
}