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

https://school.programmers.co.kr/learn/courses/30/lessons/135808?language=cpp

프로그래머스

 

이 문제는 과일의 가격이 최대 k까지 형성되어있는데 한 상자에 m개를 담아서 팔 때, 가장 많은 수익을 남기면 그 수익은 얼마인가를 계산하는 문제이다.

이 때, 한 상자에 들어있는 사과들은 가장 싼 가격의 가격으로 계산한다.

 

즉, 어떻게하면 사과가격의 손실을 최소화할 것인가가 문제인 것이다.

조금 생각해보면 답을 떠올릴 수 있다.

 

바로 최대한 같은 가격의 사과끼리 상자에 넣는 것이다. 그러면 가격 손실을 최소화시킬 수 있다.

 

그렇다면 어떻게 구현할 것인가?

이 또한 정렬을 하면 해결할 수 있다. 

 

오름,내림차순 정렬을 하면 사과의 순서가 가격에 따라 정리되기 때문에 순서대로 m개씩 상자에 담으면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

 

이 코드를 보면 오름차순 정렬 후, 끝에서부터 m개씩 상자에 담았다. 

사과개수가 12개고, m=3이라하면, i는 9부터 시작해서 6,3,0 이 된다. 

i== 9 는 상자에 9,10,11 인덱스의 상자를 넣는것이고 9가 가장 낮은가격일테니 그 가격에 m을 곱한 값을 수익에 더하는 것이다.