2512번 : 예산

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

2512번: 예산

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int arr[] = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());

        int moneyMax=0;
        int result=0;
        int start = 0, end = Arrays.stream(arr).max().getAsInt();
        //가능한 총 예산을 기준으로 이진탐색 수행
        while(start<=end) {
            int mid = (start+end)/2; //상한액
            int money=0; //가능한 총 예산
            
            //총 예산 계산
            for(int i=0;i<n;i++) {
                if(arr[i]>mid) money+=mid;
                else money+=arr[i];
            }
            
            //총 예산을 넘지않는 가능한 최대 예산이면
            if(money<=m && moneyMax<money){ 
                moneyMax = money; //예산 기록
                result=mid; //상한액 기록
            }

            if(money<m) start=mid+1; //상한액 늘려서 총 예산액 늘리기
            else if(money>m) end = mid-1; //상한액 줄여서 총 예산액 줄이기
            else break;
        }
        System.out.println(result);
    }
}

 

 

해결방법

가능한 총 예산액을 기준으로 이진 탐색을 수행하여 문제를 해결하였다.
상한액을 가지고 총 예산을 계산해 입력받은 총 예산을 넘지않는 가능한 최대 예산이면 기록을 하였다. 

그리고 계산된 총 예산(money)이 입력받은 총 예산(m)보다 작으면 총 예산을 늘리기위해 상한액을 늘렸고 
계산된 총 예산이 입력받은 총 예산보다 크면 총 예산을 줄이기위해 상한액을 줄였다.