• 풀이 방법이 비슷한 문제이다.

---

문제 이해

3가지 조건으로 예산을 분배한다.

1. 요청한 예산을 모두 분배할 돈이 존재하면 요청한 대로 나눠준다.

2. 요청 대로 돈을 줄 수 없다면 특수한 정수 K를 정한다. K이하로 요청한 사람에게는 요청한 금액만큼 돈을 주고, K보다 많이 요청한 사람에게는 K만큼만 준다.

이 때 돈을 줄 수 있는 여러 가지 상황 중 가장 많은 돈을 사용하게 하는 특정 수 K를 찾는 문제이다.

---

문제 풀이

만약 한 개 지방이 T만큼의 예산을 요청했고, K가 상한액이라고 가정하자.
그렇다면 이 지방은 얼마만큼의 돈을 받을 수 있을까?

1. T >= K : K만큼만 받을 수 있다.

2. T < K : K를 다 안줘도 되기 때문에, T만 주면 된다.

즉, T와 K중 작은 값만큼 돈을 받을 수 있으므로, 지방은 min(T,K)만큼 돈을 받을 것이다.
모든 지방이 받는 예산을 합치면 sum = $\sum{min(arr[i],K)}$가될 것이다
이 때, arr[i]는 항상 고정되어 있고 우리는 K 값만 변경시킬 수 있음을 알고 있자.
그렇다면 이 경우 상황이 2가지 존재한다. (최대로 줄 수 있는 금액 : M)

1. sum > M : 최대로 줄 수 있는 금액보다 많은 돈이 필요하기 때문에 답이 될 수 없다.
   arr[i]는 고정이므로, K를 감소시켜야하며 이를 위해 right값을 변경시킨다.

2. sum <= M : 정답이 될 수 있는 후보군이다.
   우리는 K의 최댓값을 구하고 싶기 때문에 left값을 변경시킨다.

이 때 K는 1 ~ 100000중 한 개의 값이며, 배열과는 별 관계가 없다. 즉, 배열은 Sorting시킬 필요가 없다는 것을 알 수 있다.

위 방법을 활용하여 이분탐색을 통해 문제를 해결하였다.

---

코드

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

public class Main {
	static int N;
	static Long M;
	static Integer[] arr;
	
	static void max_budget(int right) {
        // 이분 탐색을 구현한 메서드
		int left = 0;
		int mid;
		long ans = 0;
		
		while(left <= right) {
			Long sum = (long) 0;
			mid = (left + right)/2;
			
			for(int i =0;i<N;i++) {
				if(arr[i]>=mid) sum+=mid;
				else sum+=arr[i];
                // Math.min()을 직접적으로 구현한 방식
			}
			
			if(sum <= M) {
                // 문제 풀이 2번 상황
                // 답이 될 수 있는 후보이므로 답 저장(ans) 
                // & 값 증가(left값 변경)
				ans = mid;
				left = mid + 1;
			}
			else {
                // 문제 풀이 1번 상황
                // 상한액 감소 필요(right값 변경)
				right = mid - 1;
			}
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		arr = new Integer[N];
		long sum = 0;
		int right = 0;
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
			if(right < arr[i]) {
				right = arr[i];
			}
		}
	
		M = sc.nextLong();
		
		max_budget(right);
        /*
        right은 배열의 값 중 최댓값이 저장되어 있다.
        배열의 최댓값 이상으로 상한액을 배정해도 배열의 최댓값을 배정한 것과 
        동일한 효과를 낸다.
        이는 문제 이해의 1번 조건을 통해 알 수 있다.
        
        따라서, 배열 최댓값보다 큰 범위는 확인할 필요가 없다.
        */
	}
	
	static class FastReader // 입력을 빨리 받기 위한 클래스
}

---

결과

• 2,3번째 줄 틀렸습니다 : left와 right 범위를 지정할 때 right 값을 이상한 방식으로 설정하여 틀렸다.