BOJ - 2512 예산

Problem

---

Solve

총 예산을 가지고 각 지방에서 요청하는 예산을 최대한으로 배정한 최대 예산배정 값을 구하는 문제이다.

배정한 예산의 합이 총 예산을 넘어가지 않으면서 지방에서 요청하는 예산을 맞추기 위해서는 이분탐색을 사용해야한다.

즉, 배정할 예산의 최대값(최적화 문제)와 예산의 총 합이 M이하인가(결정 문제)인 매개변수탐색 문제이다.(parametric search)

start = 0, end = 각 지방 요청 예산 중 가장 큰 값으로 놓고 임의의 배정될 예산의 합이 총 예산 M을 벗어나지 않도록 한다.

임의의 예산 총 합이 M보다 작거나 같다면 start = mid, 크다면 end = mid-1로 범위를 줄여가며 조건에 만족하는 예산을 구한다.

---

Code

public class 예산 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] local = new int[N];

		//각 지방에서 요청하는 예산 중 가장 큰 값
		int maxLocal = 0;
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			local[i] = Integer.parseInt(st.nextToken());
			maxLocal = Math.max(maxLocal, local[i]);
		}
		int M = Integer.parseInt(br.readLine());

		int answer = divide(local, M, maxLocal);
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//예산 나누기(이분탐색)
	static int divide(int[] local, int M, int maxLocal) {
		int start = 0;
		int end = maxLocal;

		while (start < end) {
			int mid = (start + end) / 2 + 1;

			int sum = 0;
			for (int i = 0; i < local.length; i++) {
            	//요청 예산이 임의 예산보다 크게 책정되는 것 방지.
				sum += Math.min(local[i], mid);
			}

			//예산의 합이 총 예산보다 작거나 같다면 임의의 예산을 탐색범위에 포함시킨다.
			if(sum <= M){
				start = mid;
			}
            //예산의 합이 총 예산보다 크다면 탐색범위에서 포함시키지 않는다.
            else{
				end = mid-1;
			}
		}

		//마지막 하나 남는 예산의 총 합이 M을 넘지않는 최대로 배정할수 있는 예산
		return start;
	}
}

---

Result

---

Reference