[백준 2512] 예산 -Java

 

 

문제링크 : https://www.acmicpc.net/problem/2512

2512번: 예산

 

내 마음대로 풀이

처음 이문제를 접했을때 

'대체 상한선을 잡을 수 있는 구간을 어떻게 설정하지?' 

하며 멘붕이 왔다.

 

그래서 1부터 예산값 M까지 순차적으로 무대뽀로 때려맞추는 무모한 알고리즘을  짰는데,

M의 구간값은 1,000,000,000이라는 어마어마한 숫자범위를 가지고 있다.

그래서 큰값이 들어오면 timeout이 나버리는 문제가 있다.

 

이를 해결하기 위해서 이진탐색을 사용했다.

즉 1부터 예산값의 중간값을 구한후, 

해당 값을 상한으로 했을때 예산값 내에서 처리가능하면 

그 다음턴은 중간값+1과 예산값의 중간값을 구하고 같은 과정을 수행한다.

반대의 경우 처음값과 중간값 -1의 중간값을 구하고

다음 턴을 수행한다.

이 과정을 반복해서 나온 수가 바로 예산의 상한선이다.

코드는 아래와 같다.

 

import java.util.Scanner;
import java.util.LinkedList;

public class Main {

	static int cnt;
	static int [] n ;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 입력 받는 부분
		cnt = sc.nextInt();
		n = new int[cnt];
		int sum= 0;
		int max = 0;
		
		for (int i = 0 ; i < cnt ; i++)
		{
			n[i] = sc.nextInt();
			sum += n[i];
			if(n[i] > max)
				max = n[i];
		}
		
		int yesan = sc.nextInt();
		
		if(sum<=yesan)
		{
			System.out.println(max);
		}
		else
		{
			
			System.out.println(calculate(yesan));
		}
	}
	
	static int calculate(int yesan)
	{
		int first = 1;
		int end = yesan;
		int mid = (first + end) /2;
		int dap = 0;
		while (first <= end)
		{
			mid = (first + end) /2;
			// Invalid하다. 상한선을 더 줄여
			if (totalDistribution(mid) > yesan)
			{
				end = mid-1;
			}
			// valid 하다. 상한선을 늘려보자
			else
			{
                dap = mid;
				first = mid+1;
			}
		}
		return dap;
	}
	
	
	// 상한선의 후보값을 제공했을 떄 얻을 수 있는 총 예산액
	static int totalDistribution(int candidate)
	{
		int total = 0 ;
		for (int i = 0 ; i < cnt ; i ++)
		{
			if (candidate >= n[i])
			{
				total += n[i];
			}else{
				total += candidate;
			}
		}
		return total;
	}
}