https://www.acmicpc.net/problem/2512
import java.util.*;
import java.io.*;
public class Main
{
public static int n;
public static int limit;
public static int[] input;
public static boolean check(int num){
int sum=0;
for(int i=0; i<n;i++){
if(input[i]<=num){
sum+=input[i];
}else{
sum+=num;
}
}
if(sum<=limit){
return true;
}else{
return false;
}
}
public static int search(int max){
int l = 0;
int r= max;
int ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
l=mid+1;
ans = mid;
}else{
r=mid-1;
}
}
return ans;
}
public static void main(String[] args) throws IOException{
//입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.valueOf(br.readLine());
input = new int[n];
String[] temp = br.readLine().split(" ");
int max=0;
for(int i=0;i<n;i++){
input[i] = Integer.valueOf(temp[i]);
if(input[i]>max) max = input[i];
}
limit = Integer.valueOf(br.readLine());
int ans = search(max);
System.out.println(ans);
}
}
import java.util.Scanner;
class Main
{
static int calcTotalBudget(int[] budgets, int budgetLimit) {
int sum = 0;
for (int budget : budgets)
sum += Math.min(budget, budgetLimit);
return sum;
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] budgets = new int[N];
int maxBudget = 0;
for (int i = 0; i < N; i++) {
budgets[i] = sc.nextInt();
maxBudget = Math.max(maxBudget, budgets[i]);
}
int M = sc.nextInt();
int l = 1, r = maxBudget, ans = -1;
while (l <= r) {
int m = (l + r) / 2;
int totalBudget = calcTotalBudget(budgets, m);
if (totalBudget <= M) {
ans = m;
l = m + 1;
}
else r = m - 1;
}
System.out.println(ans);
}
}
'Problem Solving > 이진 탐색' 카테고리의 다른 글
BOJ2792 보석상자 (0) | 2024.02.28 |
---|---|
BOJ2343 기타레슨 (2) | 2024.02.28 |
BOJ2110 공유기 설치 (매개변수 탐색) (1) | 2024.02.27 |
BOJ6236 용돈관리 (매개변수 탐색) (1) | 2024.02.27 |
BOJ1654 랜선 자르기 (매개변수 탐색) (0) | 2024.02.27 |