[JAVA] 백준 2512 : 예산

문제

지방의 수 N(3<=N<=10000), 각 지방의 요청 예산, 그리고 전체 예산이 주어졌을 때,

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액 그대로 배정한다.

2. 모든 요청이 배정될 수 없으면 특정한 정수 상한액을 계산하여 배분한다.

위 규칙에 따라 예상을 배정할 때, 가장 크게 산정될 수 있는 상한액을 계산하는 문제

접근방법

1. 각 지방의 예산region[i] 을 모두 할당할 지, 상한액을 정해야할 지 판단하기 위해서는 ( 남은 지방의 수 * 해당 지방의 예산 ) 이 남은 예산을 초과하는지를 확인하면 된다.

• 예를 들어 각 지방 요청예산이 [110, 120, 140, 150] 이며, 전체 예산이 485일 때, region[0] 을 볼 때, 나머지 예산들은 모두 110보다는 같거나 크므로, 가장 작아봐야 모두 110이 된다. 이 때, 110*4 는 전체 예산인 485를 넘지 않으므로 110을 모두 할당할 수 있다.

• 110을 할당한 뒤, 전체 예산은 375가 남고, 그 다음 지방예산인 120을 본다. 남은 지방은 3개가 남았고 모두 가장 작아도 120이므로, 120 * 3을 하면 역시 남은 예산인 375보다 작으므로 해당 지방에도 예산을 모두 배정할 수 있다.

• 다음 3번째 지방을 보면, 남은 예산은 255가 남았으며 지방은 2개가 남았다. 140 * 2를 하면 남은 예산을 초과하게 되므로 예산을 모두 할당해 줄 수 없고 상한선을 설정해야 한다.

• 상한선은 남은 예산을 최대한 많이 사용하는 값으로 정해야 하므로, 몇 개의 지방에 배정해주고 남은 예산을 남은 지방에 동일하게 나누어주고 나머지를 버리면 최대 상한값을 얻을 수 있다.

2. 모든 예산을 배정해줄 수 있을 때의 상한값은 가장 큰 지방 요청 예산이 된다.

• 배열을 정렬하면 상한값은 region[N-1]이 된다.

소스코드

Scanner sc = new Scanner(System.in);
​
int N = sc.nextInt();
int[] region = new int[N];
for(int i=0; i<N; i++)
        region[i] = sc.nextInt();
​
Arrays.sort(region);
​
int budget = sc.nextInt();
int limit = 0;
for(int i=0; i<N; i++){
        if(region[i] * (N-i) < budget){
                budget -= region[i];
        }else{
                limit = budget/(N-i);
                break;
        }
}
​
// 모두 예산을 배정할 수 있는 경우
if(limit == 0)
        limit = region[N-1];
​
System.out.println(limit);
​