https://www.acmicpc.net/problem/2512
분류 : 이분 탐색
더보기
public class Main {
public static PrintWriter out;
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int N = sc.nextInt();
int[] contry = new int[N];
int Tsum = 0;
int Tmax = 0;
for(int index = 0; index<N;index++){
contry[index] = sc.nextInt();
Tsum+= contry[index];
Tmax = Math.max(Tmax, contry[index]);
}
long budget = sc.nextLong();
int s = 1;
long max =0;
long e = 1000000001;
if(Tsum<=budget){
out.println(Tmax);
}
else{
while(s+1<e){
long sum =0;
int mid = (int) ((s+e)/2);
for(int index=0;index<contry.length;index++)
{
if(mid>=contry[index]){
sum +=contry[index];
}
else{
sum+=mid;
}
}
if(sum>budget){
e = mid;
}
else{
s = mid;
}
}
out.println(s);
}
out.flush();
}
}
문제 풀이 : 최저 예산 1부터 최고 예산 1,000,000,000을 정해놓고서 이분 탐색을 통해 최대 예산을 추적해간다!
중간 지점(Mid)을 정해서 각각의 필요 예산과 비교하여 크면 필요 예산을 더하고 작다면 mid를 더한 후 Sum 값이 주어진 전체 예산과 비교 판단한다.
이때 , sum> budget이라면 최고 예산을 mid로 sum <=budget이라면 최저 예산을 mid로 대입한 후에 이분 탐색을 계속 반복하다 보면 답이 나온다.
처음 제출 후 틀렸을때 간과했던 것이 있다면 , 지방에서 각각 요구하는 예산의 합이 전체 예산보다 작다면 그냥 지방의 요청 예산중 최댓값을 답으로 출력하면 된다..
'PS' 카테고리의 다른 글
[BOJ] 2568번 : 전깃줄 - 2 (0) | 2017.06.01 |
---|---|
[BOJ] 1051번 - 숫자 정사각형 (0) | 2017.05.29 |
[BOJ]2526번 : 싸이클 (0) | 2017.05.01 |
[BOJ]1660번 : 캡틴 이다솜 (0) | 2017.04.26 |
[BOJ]5052번 : 전화번호 목록 (0) | 2017.04.24 |