광물 캐기(그리디)

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

 

어떤 기준으로 그리디 하게 접근해야 하는지 고민해 봐야 하는 문제다.

 

모든 광물에 대해서 다이아, 철, 돌 곡괭이 순서로 피로도 소모가 적다. → 그리디

다이아, 철, 돌 곡괭이중 모든 광물에 대해 다른 값을 갖고있는 것은 돌 곡괭이 뿐이다. → 기준

 

즉, 각 광물에 대해서 돌 곡괭이로 캤을때의 피로도를 구하고

돌 곡괭이로 캤을때 가장 피로도가 높은 광물들 먼저 다이아->철->돌 곡괭이 순서로 사용해서 그리디하게 접근해야한다.

 

이런 과정에서 광물을 5개 단위로 캐야한다는 점, 곡괭이를 전부 사용한 이후의 광물에 대해선 캘 수 없다는 점에 유의하여야 한다.

 

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

bool comp(vector<int>& vec1, vector<int>& vec2)
{
    return vec1[2] > vec2[2];
}

int solution(vector<int> picks, vector<string> minerals)
{
    vector<vector<int>> mine;
    int mine_length = minerals.size();
    int dia = 0;
    int iro = 0;
    int sto = 0;
    // 5개 단위로 각 곡괭이마다 피로도량으로 정리해준다
    for (int i = 0; i < mine_length; i++)
    {
        string next = minerals[i];
        if (next == "diamond")
        {
            dia += 1;
            iro += 5;
            sto += 25;
        }
        else if (next == "iron")
        {
            dia += 1;
            iro += 1;
            sto += 5;
        }
        else
        {
            dia += 1;
            iro += 1;
            sto += 1;
        }
        if ((i + 1) % 5 == 0 || i == mine_length - 1)
        {
            mine.push_back({ dia, iro, sto });
            dia = iro = sto = 0;
        }
    }
    // 현재 곡괭이들로 캘 수 있는 구간만 남겨둔다
    int total_pickage = picks[0] + picks[1] + picks[2];
    while (mine.size() > total_pickage) mine.pop_back();
    // 돌 곡괭이로 캤을때 피로도를 기준으로 내림차순 해준다
    sort(mine.begin(), mine.end(), comp);
    // 돌 곡괭이로 캤을때 가장 많은 피로도를 소모하는 광물들부터 다이아->철->돌 순서로 사용한다
    int answer = 0;
    for (vector<int>& vec : mine)
    {
        if (0 < picks[0]--)
        {
            answer += vec[0];
        }
        else if (0 < picks[1]--)
        {
            answer += vec[1];
        }
        else if (0 < picks[2]--)
        {
            answer += vec[2];
        }
        else break;
    }
    return answer;
}