[백준 2512] 예산- java (solved.ac - 실버 3)

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

2512번: 예산

풀이

문제를 보았을 때 알 수 있는 힌트

문제를 보면 예산을 분배하는데 최대로 분배하는 방법을 구하는 문제이다.

2가지 조건을 고려해서 계산을 진행해야한다.

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

2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다.

이 두가지만 고려하면 된다.

단순하게 예산을 0부터 1씩 올리다보면 언젠가는 최대의 값을 찾을수 있을 것이다.

하지만 그렇게 푼다면 시간초과가 날것이다.

그렇기에 최대값을 정하고 0과 그 사이값을 찾고 이분 탐색으로 풀면 문제를 O(logn)으로 문제를 풀 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n,n_list[],m;
	static int start,end;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token;
		n = Integer.parseInt(br.readLine());
		n_list = new int[n];
		token = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			n_list[i]=Integer.parseInt(token.nextToken());
		}
		m = Integer.parseInt(br.readLine());
		Arrays.sort(n_list);
		end = n_list[n-1];
		
		while(start<=end) {
			int mid = (start+end)/2;
			long sum = 0;
			for (int i = 0; i < n; i++) {
				if(n_list[i]<=mid) {
					sum+=n_list[i];
				}
				else {
					sum+=mid*(n-i);
					break;
				}
			}
			if(sum<=m) { // 초과 하지 않은 경우
				start = mid+1;
			}
			else { // 초과 했을 경우
				end = mid-1;
				
			}
		}
		System.out.println(end);
	}

}

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/java/baekjoon2512/Main.java

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리