[Level 1] 예산

 

 

 

Algorithm

-  예산 -

 

---

 

문제

S사에서는 각 부서에 필요한 물품을 지원해주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다.

그러나, 전체 예산이 정해져있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다.

그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

 

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다.

예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원 보다 적은 금액을 지원해 줄 수는 없습니다.

 

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 함수를 완성해주세요.

 

입출력 예시

d	budget	result
[1, 3, 2, 5, 4]	9	3
[2, 2, 3, 3]	10	4

 

문제 풀기

 

이번 문제는 정해진 예산으로 얼마나 많은 부서에게 나눠줄 수 있느냐에 대한 문제로 문제의 길이가 길어서 조금 겁을 먹었으나 풀때는 다행히 엄청 어려운 편은 아닌것 같았다.

 

일단 최대한 많은 부서에게 나눠주는 방법은 가장 적은 금액을 신청한 부서들에게 나눠주는게 큰 금액을 신청한 부서들에게 나눠주는 것 보다 더 많은 부서에게 나눠줄 수 있을거라고 생각해서 일단 d에서 배열로 받아오는 금액을 오름차순으로 정렬을 시켜주었다.

 

그리고 leftMoney와 count라는 변수를 만들어서 반복문을 통해 남은 예산을 확인할 수 있도록 leftMoney안에 값을 넣어주고, 예산을 부서에게 나눠줄때 마다 카운트를 올릴수 있도록 count안에 값을 넣어주었다.

 

그 이후 반복문안에서 예산을 나눠주고 count를 올려주는 방식으로 진행시켜주며 이때 left머니가 0보다 작은값이 나올경우 (= 예산 없음) break문을 사용해 반복문을 벗어나고 count를 최종적으로 리턴할 수 있도록 함수를 만들어 주었더니 문제가 제대로 해결되는 것을 확인할 수 있었다.