본문 바로가기

PS

[BOJ] 2512번 - 예산

https://www.acmicpc.net/problem/2512

 

2512번: 예산

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상

www.acmicpc.net


 

분류 : 이분 탐색

 

더보기
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