Lv1_[과일 장수, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

사과박스의 가격은 박스에 들어가 있는 사과 중 최하품 사과 가격으로 정해진다.
그렇기 때문에 가격이 높은 것끼리 박스에 포장으로 하는 것이 가격을 가장 높게 받는 방법이다.

 

· 사과가 저장되어 있는 "vector<int> score"를 내림차순으로 정렬
· m개씩 사과를 포장했을 때, index가 큰 것이 가장 낮은 가격이 됨

 

[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]를 내림차순으로 정렬을 하면

 

index [2, 5, 8, 11]의 가격을 m과 곱한 값을 모두 더하면 최대 이익을 만들 수 있다.

 

※ 조건 중 고려할 사항
- 사과 박스에 m개 미만의 사과가 들어가면 안 됨
- k 매개변수는 사용되지 않음

 

 

#include <string>
#include <vector>
#include <algorithm>    // sort, greater<> 사용
 
using namespace std;
 
int solution(int k, int m, vector<int> score) {
    int answer = 0;
 
    int index = m - 1;  // index가 0부터 시작하기 때문에 -1을 해줌
    unsigned int score_size = score.size();
 
    // 내림차순 정렬
    sort(score.begin(), score.end(), greater<int>());
 
    while(true) {
        // 박스에 m개를 채울 수 없으면 종료
        if(index > score_size) {
            break;
        }
        answer += (score[index] * m);
        index += m;
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓