AlgorithmProgrammers

프로그래머스 예산

, , ,

1. 문제 링크

프로그래머스 예산

2. 문제 조건

  • d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
  • d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
  • budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

3. 컴퓨팅 사고

이문제를 풀기 위해서 가장 중요한것은 처음에 이것을 DFS로 풀어야하나? 라는 생각을 했다는 것입니다. 최대 몇 개의 부서에 물품을 지원 이라는 말에서 dfs를 통한 모든 개수를 구한 후 *max_element를 사용해서 값을 구하면 되지 않을까 라는생각을 하였습니다. 하지만 이 문제는 순열과 조합의 문제가 아니라 단순히 구현문제였습니다.

모든 예산을 sort()정렬을 시킨 후 가장 작은 예산의 문제부터 풀어나가면서 answer의 값을 +1 씩 늘려가면 최종적으로 최대 구할 수 있는 예산의 수를 확인할 수 있습니다.

그리고 budget 현재 예산에서 d[i]만큼을 값을 빼주면서 계속 진행해 나가면 됩니다. 작은값부터 이루어져 나가니 다른 경우는 신경쓸 필요가 없다는 것입니다.

왜 이것을 DFS로 풀려고 했을까? 맨처음 basement cnt를 둘까 sum을 둘까라는 고민을 하게되었는데 너무 어렵게 생각을 하게 되었습니다. 여러 조합을 끼워맞춰서 가장 큰 값을 구하려고 하였던것이 오류였습니다. 단순히 정렬한번만으로도 충분히 풀 수 있었던 그런 문제였습니다.

요약

그리디 알고리즘을 사용해서 d의 각 원소는 부서별로 신청한 금액을 오름차순 정렬 후 적은금액부터 예산을 처리합니다. 그리고 d의 요소들과 budget을 비교해나가면서 예산금액을 (budget - d)로 연산하면서 나갑니다. 단, budget이 0보다 클 경우에만 가능합니다.

4. 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(int a,int b){
    return a < b;
}
int solution(vector<int> d, int budget) {
    int answer = 0;
    
    sort(d.begin(), d.end(), cmp);
    
    for(int i=0; i<d.size(); i++){
        if(budget - d[i] >= 0){
            answer +=1;
            budget = budget - d[i];
        }
        
    }
    
    return answer;
}
Share