[코딩테스트 연습]예산

 

문제: https://programmers.co.kr/learn/courses/30/lessons/43237

---

이분 탐색 문제입니다.

 

지방의 갯수를 M개라 한다면, 정해진 예산으로 할당이 가능한지 판단하는데 O(M)이 걸립니다.

 

그러므로 예산을 정하는 로직을 로그시간에 처리해야합니다. 그래서 이분탐색이 필요합니다.

 

한 가지 주의해야 할 것은 오버플로우 입니다.

예산의 총액 상한액이 10억이지만, 

mid = (lower + upper ) / 2 를 구하는 과정에서 lower + upper는 INT 범위를 초과할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43237.cc