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

문제설명

해당 문제는 주어진 값에서 얻을 수 있는 최대 가치를 계산하는 문제이다

상자에 과일의 가치가 주어지면 한 상자에 들어갈 수 있는 과일의 수와 최대 과일의 가치 값을 입력받는다

 

알고리즘

1. 과일의 가치를 내림차순으로 정렬한다

2. 팔 수 있는 최대의 상자 수 만큼 반복문을 돈다(남는 과일은 버리기 때문에 완성되는 상자 기준으로 계산한다)

3. 각 상자마다 가장 가치가 낮은 것이 얻을 수 있는 값이기 때문에 각 상자마다 제일 가치가 낮은 인덱스에 접근해서 결과 값을 계산한다  

코드

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

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    
    //내림차순 정렬
    sort(score.begin(), score.end(),greater<>());

	//상자에서 제일 가벼운 것의 값* 상자에 들어간 과일의 수 
    for(int i=1; i<=score.size()/m; i++){
        answer += m * score[m*i-1];
    }  
    
    return answer;
}

고찰

처음에 문제를 이해하고 알고리즘을 짜는데 복잡해 질 수 있지만 의외로 반복문으로 해결가능하다

먼저 최대 가치를 반환해야하기 때문에 내림차순으로 정렬하는게 필수이다

그리고 한 상자당 넣을 수 있는 과일의 수가 정해져 있기 때문에 남는 경우 버리는 부분을 감안하면 내림차순이 옳다는 판단에 힘을 싣어 준다

내림차순이기 때문에 그 상자에 가장 끝부분(인덱스로 감안하면 제일 큰 값)이 그 상자의 가치가 된다

그 후 위의 문제에서 주어진 식에 대입하면 간단하게 풀 수 있는 문제였다