알고리즘/이분 탐색
백준 2512번: 예산 (JAVA) <이분 탐색>
눈사람99
2023. 3. 31. 16:58
728x90
문제 해석
국가예산 총액 M
지방의 수 N
각 지방에서 요청하는 예산이 입력값으로 주어진다.
M이 요청하는 예산을 다 수용할 수 있을만큼 크면 요청하는대로 예산을 분배해주지만
다 수용이 불가능하다면 상한선을 설정하여 상한액보다 큰 금액을 요청하는 지방에는 상한액을 배정하고 이외에는 요청하는대로 처리한다.
알고리즘
모든 경우를 다 찾아보려다 좀 아닌거 같아서 힌트를 참고하였는데
이 문제는 이분 탐색을 통해 원하는 값을 찾는 문제였다.
이분 탐색은 정렬되어 있는 리스트를 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다.
이분 탐색을 위해 이 문제에서는 left 변수를 0, right 변수를 요청액 중 가장 큰 값으로 설정하고 범위를 좁혀가며 적절한 값을 찾아가면 된다. 조건에 따라 left를 증가시키거나 right를 감소시켜 범위를 좁혀 left > right 가 되기 전까지 수행한다.
출력해야하는 값은 가능한 상한액을 크게한 값이다.
예산 배정 조건 중 첫번째 조건은 문제 풀이 시 고려하지 않아도 이분 탐색 상한액 찾기로 자동 고려된다.
ex) 지방 요청액이 각각 100 100 100 이고 총 예산이 300일 시 원래는 상한액 조건이 필요없이 100씩 분배해주면 되지만
현재 알고리즘에서 이분 탐색으로 상한액 선정 시 위 경우는 100이 상한액인 경우로 처리된다.
따라서 따로 분리해 생각할 필요없이 상한액 선정을 최대화하는 것에 집중하면 된다.
코드
728x90