2512_예산

사용 알고리즘: 파라메트릭 이분탐색

사용 언어: java

 

파라메트릭 이분탐색 문제를 연속으로 해결하고 나니, 내가 이 알고리즘을 이제 어느정도 다룰 수 있다는 생각이 들었다.

진짜..... 처음엔 너무 이해가 안 가서 힘들었던 알고리즘이었는데!

 

package week21;

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

public class Main {
	static int n;
	static int[] arrs;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		arrs = new int[n];
		for(int i=0; i<n; i++) {
			arrs[i] = sc.nextInt();
		}
		Arrays.sort(arrs); //최대값 한 번에 찾기 위함 그 이상 그 이하도 아님
		int 예산 = sc.nextInt();
		
		int ans = 1;
		int left = 1;
		int right = arrs[n-1];
		while(left <= right) {
			int mid = (left+right) / 2;
			int sov = solve(mid);
			if(sov <= 예산) {
				ans = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		System.out.println(ans);
	}

	private static int solve(int mid) {
		int total = 0;
		for(int i=0; i<n; i++) {
			if(mid < arrs[i])
				total += mid;
			else
				total += arrs[i];
		}
		return total;
	}

}