Java) 프로그래머스 - 예산
문제 링크
문제
- 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.
- 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
- 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.
- 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
- 각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.
제한
- 지방의 수는 3 이상 100,000 이하인 자연수입니다.
- 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
- 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.
👀 풀이
-
뭔가 막연하게 이분탐색 문제같았는데 범위를 좁혀나가는 기준을 어떻게 설정해야 할 지 모르겠어서 풀이 영상을 봤다. 이분탐색 문제는 풀 때마다 어렵게 느껴진다 😭
- 문제를 풀기 위해서는 금액이 최대가 되는 상한액의 범위를 좁혀가면서 탐색해야 한다. 그래서 최소값(0)과 최대값(입력 중 가장 큰 값) 범위에서 중간값을 구한 다음 이 중간값이 적절한 상한액이면 정답이 되는 것이고 많이 모자란 값이라면 최소값을 증가시키고, 초과하는 값이라면 최대값을 감소시킨다.
- 이 과정을 최소값과 최대값이 같아지는(서로 만나는) 지점까지 반복하면 된다.