문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
부서 별로 예산을 지원해준다. 짤라주기는 불가능 필요한 예산은 전액만 지원 가능
예를 들어 1000원이 필요한 부서에는 1000원을 지원해야함. 500원 지원 불가.
전체 예산이 정해져 있을 때, 최대한 많은 부서를 지원하자!
부서별 신청 금액 : d
전체 예산 : budget
1 <= d의 길이 <= 100
1 <= d 원소의 크기 <= 100,000
1 <= budget <= 10,000,000
입출력 예시
| d | budget | return |
|---|---|---|
| [1, 3, 2, 5, 4] | 9 | 3 |
| [2, 2, 3, 3] | 10 | 4 |
접근
필요 예산이 적은 부서 순으로 지원을 해주면, 가장 많은 부서들이 지원받을 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
def solution(d, budget):
d.sort()
answer = 0
for i in d:
if budget >= i:
budget -= i
answer += 1
else:
break
return answer
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector<int> d, int budget) {
int answer = 0;
sort(d.begin(), d.end());
for(int i = 0; i<d.size(); i++){
if(budget >= d[i]){
budget -= d[i];
answer += 1;
}
else{
break;
}
}
return answer;
}