[프로그래머스] 과일 장수 C++

13 Feb 2023 in Study on Coding Test

그리디 알고리즘 문제

정답제출코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    
    vector<int> temp = score;
    
    sort(temp.begin(), temp.end());
    
    while (temp.size() >= m)
    {
        vector<int> box;
        
        for (int i = 0; i < m; ++i)
        {
            box.push_back(temp[temp.size()-1]);
            temp.pop_back();       
        }
        
        answer += m * box[m-1];
    }
    
    return answer;
}

• 한 상자에 최대한 높은 사과를 담는 것이 유리하다.
• 그래서 temp에 score을 복사하고, 오름차순으로 정렬시켰다.
• 끝에서 부터 박스에 m개를 담아준다.
• 그리고 오름차순으로 정렬된 상태에서 끝에서부터 담으면 무조건 나중에 담은 것이 가장 점수가 낮을 것이다. (box[m-1]에 해당함.)
• 그래서 box[m-1] * m을 answer에 더해준다.
• 과정에 끝나면 answer을 리턴한다.