이 문제는 제한된 국가예산을 예산요청에 맞추어 분배 가능한 최대 상한액을 구하는 문제이다. 우선 모든 예산요청을 국가예산으로 받아들일 수 있다면 예산요청 중 최댓값을 출력한다. 이 외의 경우는 몇 개의 예산요청을 제한하는 상한액을 구해야 한다.

가장 쉬운 방법으로는 상한액을 1씩 증가시켜가면서 국가예산의 배분이 가능한지 불가능한지를 알아보는 방법으로 예산요청이 개 이고 답이 일 때 의 시간복잡도를 가진다. 이 방법은 낮은 점수를 받는다. 답 를 이분검색으로 찾으면 의 시간복잡도로 해결할 수 있는데, 이 방법은 만점을 받는다.

다른 방법으로는 상한액을 예산요청을 하나씩 포함하도록 하면서 가능한 최대의 상한액을 구하는 방법이다.

상한액을 라고 하고 상한액 보다 작은 예산요청들의 합을 , 개수를 이라고 하면 이에 필요한 국가예산은 이다.

여기서 주어진 국가예산 보다 작은 부분을 이용해 상한액을 높일 수 있는데 새로운 상한액은 로 구할 수 있다. 이 과정을 작은 예산요청부터 순서대로 진행하면 가능한 최대의 상한액을 구할 수 있다. 이는 예산요청을 또는으로 정렬하고 나면 에 구할 수 있다. 즉,또는의 시간복잡도로 문제를 풀 수 있다.

의 시간복잡도로 구할 경우 만점을 받을 수 있다.

koi_budget 대회 풀이