문제
문제 설명
지방의 수 N 이 주어지고 각 지방에서 요구하는 예산이 주어진다.
이때 정부의 예산 총액이 M 이라고 주어질 때 예산안에 맞게 예산을 배정하고 예산 중 최댓값인 정수를 출력하는 프로그램이다.
각 지방에서 요구하는 예산의 총액이 정부 예산 총액보다 적다면 그냥 다 배정하고 그렇지 않다면 정수 상한액을 계산하여 이 금액보단 높지 않게 해주면 된다.
구현
적절한 금액을 정해주면 될 것 같아서 이분탐색으로 방향을 잡았다.
처음에 생각한 거는 배열을 정렬해서 그 사이에서 최솟값과 최댓값 사이에서 금액을 정해주면 된다고 생각했는데 일반적인 테스트 케이스에서는 통과하겠지만 일부 반례가 있을 것 같아서 최솟값은 0으로 하고 최댓값은 예산의 최대인 100,000 으로 설정하고 풀었다.
일단 맨처음에 주어진 값들의 합인 sum이 예산인 m 보다 작다면 그 중 최댓값을 구하고 return을 해주었다.
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
max = Math.max(arr[i], max);
}
Arrays.sort(arr);
m = Integer.parseInt(br.readLine());
if (sum <= m) {
System.out.println(max);
return;
}그 후에는 이제 이분탐색을 사용하여 적정값을 찾아야 한다.
위에서 말한대로 left 는 0으로 두고 right 는 100,000 으로 두고 시작한다.
여기서 위에서 구했던 max 값이 중복으로 들어가는 걸 방지하기 위해서 다시 0으로 초기화 해준다.
int left = 0;
int right = 100_000;
max = 0;그리고 나서 left < right 조건 아래에서 값을 비교해준다.
mid = (left + right) / 2 로 중간 값을 찾아주고 기존 배열을 변경하면 안되기 때문에 temp 배열에 기존 배열을 복사하고 현재 기준 값인 mid 보다 크면 값을 변경해주고 sum 에 더해준다.
그리고 이 sum 변수가 예산안 이하이면 수용가능하기 때문에 max 를 mid 값으로 변경해주고 더 작은 값이 있는지 확인하기 위해 left 를 mid + 1 로 변경해준다.
그렇지 않다면 더 작은 값을 시도해야 하기 때문에 right를 mid - 1 로 바꾸고 다시 시도해준다.
코드
import java.io.*;
import java.util.*;
public class Main_2512 {
static int n, m;
static int[] arr;
static int sum;
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
max = Math.max(arr[i], max);
}
Arrays.sort(arr);
m = Integer.parseInt(br.readLine());
if (sum <= m) {
System.out.println(max);
return;
}
//이분탐색으로 적정값 찾기
int left = 0;
int right = 100_000;
max = 0;
while (left <= right) {
sum = 0;
int mid = (left + right) / 2;
int[] temp = new int[n];
//정수 상한액 반영 후 예산안의 합을 구함
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
//만약에 이분탐색 값보다 크다면
if (temp[i] > mid) {
temp[i] = mid;
}
sum += temp[i];
}
//만약 합이 예산안에 있으면 더 작은값이 있는지 확인
if (sum <= m) {
max = mid;
left = mid + 1;
}
//조건을 초과하면 더 작은 값 시도
else right = mid - 1;
}
System.out.println(max);
}
}