[Kickstart][2020][Round A] 1. Allocation

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56

---

N 개의 집이 판매중이고, 각 집의 판매가격이 주어진다.

내가 B 달러를 가지고 있을 때, 최대 몇 채의 집까지 살 수 있는가?

---

구입할 수 있는 최대 개수의 집을 구하려면 가격이 작은 집들부터 구입하면 된다. -> 그리디 문제이다.

판매 가격을 오름차순 정렬한다.

앞에서부터 탐색하면서 B 달러로 탐색 중인 집을 구입할 수 있다면 정답 +1 을 해주고 B달러에 구입한 집 가격을 빼준다.

탐색 중인 집을 남은 달러로 구입할 수 있다면 판매 가격을 오름차순 정렬했기 때문에 이후에 나올 집들도 구매할 수 없을 것이다.

따라서 탐색을 종료하고 이때까지 구매한 집들의 개수가 정답이 된다.

 

시간복잡도는 정렬하는데 가장 오랜 시간이 소요되므로 O(NlogN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundA/1.%20%20Allocation.cpp