백준 2512번: 예산 (JAVA) <이분 탐색>

 

문제 해석

 

국가예산 총액 M

지방의 수 N

각 지방에서 요청하는 예산이 입력값으로 주어진다.

M이 요청하는 예산을 다 수용할 수 있을만큼 크면 요청하는대로 예산을 분배해주지만

다 수용이 불가능하다면 상한선을 설정하여 상한액보다 큰 금액을 요청하는 지방에는 상한액을 배정하고 이외에는 요청하는대로 처리한다.

 

알고리즘 

 

모든 경우를 다 찾아보려다 좀 아닌거 같아서 힌트를 참고하였는데

이 문제는 이분 탐색을 통해 원하는 값을 찾는 문제였다.

이분 탐색은 정렬되어 있는 리스트를 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다.

이분 탐색을 위해 이 문제에서는 left 변수를 0, right 변수를 요청액 중 가장 큰 값으로 설정하고 범위를 좁혀가며 적절한 값을 찾아가면 된다. 조건에 따라 left를 증가시키거나 right를 감소시켜 범위를 좁혀 left > right 가 되기 전까지 수행한다.

출력해야하는 값은 가능한 상한액을 크게한 값이다.

예산 배정 조건 중 첫번째 조건은 문제 풀이 시 고려하지 않아도 이분 탐색 상한액 찾기로 자동 고려된다.

ex) 지방 요청액이 각각 100 100 100 이고 총 예산이 300일 시 원래는 상한액 조건이 필요없이 100씩 분배해주면 되지만

현재 알고리즘에서 이분 탐색으로 상한액 선정 시 위 경우는 100이 상한액인 경우로 처리된다.

따라서 따로 분리해 생각할 필요없이 상한액 선정을 최대화하는 것에 집중하면 된다.

 

코드