[200516] 예산 - Summer/Winter Coding(~2018)(level1)

1. 문제이해

- 배열 d : 부서별 신청한 금액 배열

- budget : 예산

- 예산 내 지원할 수 있는 부서 개수의 최대값 구하기

(단, 일부금액만 지원하는 것은 불가)

 

2. 전략

- Greedy algorithm 이용 : 각 단계에서 "가장 좋은 것" 선택

(최대한 많은 부서 지원 = 신청 금액이 적은 부서부터 선택)

- d를 오름차순 배열한 순서대로 지원해주면 됨

- 지원해줄 때마다 budget을 줄여가며 신청금액이 budget을 넘지 않을 때까지만 진행(for문)

 

3. 참고사항

- 유사, 심화 문제 : Fractional Knapsack Problem

- 문제 : 물건들의 무게wi, 가치vi + 배낭무게 W --> 최대이득으로 물건 넣기
(단, 물건의 분할이 가능 = Fractional)
- 해결방법 : 각 단계에서 "가장 좋은 것" = 무게당 가치가 가장 높은 것(vi/wi)부터

 

4. 코드

import java.util.*;
class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        //Greedy
        Arrays.sort(d);
        for(int a : d){
            if(a <= budget){
                budget -= a;
                answer++;
            }
            else    break;
        }
        return answer;
    }
}