알고리즘/프로그래머스 1단계
프로그래머스 - 과일 장수 - C++
게임만드는학생
2025. 4. 24. 15:39
https://school.programmers.co.kr/learn/courses/30/lessons/135808?language=cpp
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
이 문제는 과일의 가격이 최대 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을 곱한 값을 수익에 더하는 것이다.