boj 2512 : 예산

boj 2512 : 예산

2개의 이분탐색으로 해결.

1. 총 예산(M)을 벗어나지 않는 상한액의 최대값을 이분탐색.

2. 상한액이 주어질 때의 예산합을 이분탐색으로 구현

2-1. 요청비용들을 오름차순으로 정렬한 후 정렬된 요청비용배열 a에 대해 psum배열을 만들어줌 (psum[i] : i번째 요청까지의 금액)

2-2. a[i] <= '상한액'인 최대 i를 이분탐색으로 찾음.

2-3. psum[i] + (N-i)*money 가 money일떄의 예산합

K를 주어진 요청 중 최대비용이라 할 때,

시간복잡도는 NlogN(정렬) + log(K)*log(N)으로 NlongN.

ㅜㅜ이분 탐색 너무 헷갈린다

많이 풀어봐야할듯