[백준/Java] 2512 예산
조건
-
지방의 수 N개 주어진다. (3 <= N <= 10,000)
-
각 지방마다 요청하는 예산이 N개 만큼 주어진다. (1 <= 예산 <= 100,000)
-
총 예산이 주어진다.(최대 값은 10억이다)
예제 입력
해설
이 문제는 이분탐색으로 해결 할 수 있는데 범위는 예산을 요청한 값들중에 가장 큰 값을 넣으면 된다. 각 지방마다 요청하는 예산 값이 총 예산보다 낮아야 하기 때문에 범위의 최대값이 예산들 값중에서만 제일 크면 된다. 그 후 전체 예산을 탐색하며 mid 값 vs 요청예산 둘 중에서 낮은 값을 넣어 sum 값이 전체 예산을 초과하는지 확인하면 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
static int[] A;
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static void input() {
N = scan.nextInt(); // 지방의 수를 받는다.
A = new int[N + 1]; // index를 1부터 시작하기 위해 +1을 해준다.
for(int i=1;i<=N;i++) {
A[i] = scan.nextInt(); // 지방이 요청하는 예산을 받는다.
}
M = scan.nextInt(); //총 예산을 받는다.
}
static boolean findAns(int buget) {
int sum = 0;
for(int i=1;i<=N;i++) {
sum += Math.min(A[i],buget); // 요청 예산과 mid을 비교하여 더 낮은 값을 //넣어주고 sum을 해 총 예산보다 작다면 true를 반환한다.
}
return sum <= M;
}
static void find() {
int ans =0, L =0, R = 0;
for(int i =1;i<=N;i++) {
R = Math.max(R, A[i]); // 탐색 범위의 최대값은 요청 예산에서 제일 큰값으로 해주 // 다
}
while(L <= R) {
int mid = (L + R) / 2;
if(findAns(mid)) {
ans = mid; //true이면 ans에 mid값을 넣고
L = mid + 1; // 범위를 줄여준다.
} else {
R = mid - 1;
}
}
System.out.println(ans);
}
public static void main(String[] args) {
input();
find();
}
static class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch(IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
Long nextLong() {
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
}catch(IOException e) {
e.printStackTrace();
}
return str;
}
}
}
Author And Source
이 문제에 관하여([백준/Java] 2512 예산), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heetaeheo/백준Java-2512-예산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)