[프로그래머스] 예산

---

1. 문제 이해

- 회사의 총 예산(budget) 은 정해져 있다.

- 각 부서는 원하는 요청 금액(d) 을 제출한다.

- 부서는 요청한 금액만큼 정확히 받아야 하며, 덜 줄 수는 없다.

- 최종 결과: 최대한 많은 부서를 지원하는 것

---

2. 문제 접근 방법

- 금액이 큰 부서부터 지원하면 예산이 빨리 소진되어 지원 가능한 부서 수가 줄어들기 때문에 작은 금액부터 지원하도록 한다.

예시1
- 요청 금액: [1, 3, 2, 5, 4]
- 예산: 9

- 정렬 전: [1, 3, 2, 5, 4] → 정렬 후: [1, 2, 3, 4, 5]
- 순서대로 합산
   - 0 + 1 = 1 (1 지원)
   - 1 + 2 = 3 (2 지원)
   - 3 + 3 = 6 (3 지원)
   - 6 + 4 = 10 → 예산 초과, 중단

☑︎ 총 3개 부서 지원 가능

---

3. 문제 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        
        // 신청 금액이 작은 부서 부터 진행 하도록(오름차순)
        // 그래야 최대한 많은 부서의 물품을 구매할 수 있음
        Arrays.sort(d);
        
        int budgetSum = 0;      // 예산 합계
        int divisionCount = 0;  // 신청 부서 수
        
        for (int requestBudget : d) {
            if (budgetSum + requestBudget > budget) {
                break;
            }
            
            // 예산이 넘지 않으면
            // 요청 예산을 예산 합계에 합산 -> break 걸릴때까지
            budgetSum += requestBudget;
            
            // 신청 부서 수 카운트
            divisionCount++;
        }
        
        // 최종 지원 가능한 부서 수 return
        return divisionCount;
    }
}

---

4. 실행 결과

- 입력: d = [1,3,2,5,4], budget = 9 → 결과: 3

- 입력: d = [2,2,3,3], budget = 10 → 결과: 4

 

 

---

 

프로그래머스 문제 링크

참고 블로그

GitHub 풀이 코드