문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

곡괭이로 광물을 캔다.
곡괭이는 총 3가지로 각각의 피로도는 고정되어 있다.
- 모든 곡괭이는 5개의 미네랄을 캘수 있음.
- 5개를 캐는 중간에 다른 곡괭이를 사용할 수 없음.
미네랄의 순서가 주어지고, 이 순서는 변경할 수 없다.
미네랄은 최대 50개, 곡괭이는 각각 최대 5개

2. 알고리즘 설계

문제를 보자마자 직감했다. 이건 그리디.
문제는 광물의 순서가 고정되어 있어 순차적으로 탐욕 접근이 불가능
- 곡괭이를 집어들면, 무조건 5개의 미네랄을 캐야한다.
- 5개씩 쪼개면 순서를 지키지 않아도 된다!
피로도가 높은 5개의 광물을 다이아 곡괭이부터 소모시키는 게 가장 이상적
- 피로도 순으로 정렬하면 되겠구나!
- 이전 문제에서 사용했던 priority_queue(pq) 사용

구조체 정의

피로도의 총합이 큰 순이므로, operator의 부호가 일치한다.

struct Weight
{
    int sum;
    int arr[3];
      
    Weight(int dia, int iron, int stone) {
        sum = dia + iron + stone;
        arr[0] = dia, arr[1] = iron, arr[2] = stone;
    }
      
    bool operator< (const Weight &other) const {
        return sum < other.sum;
    }
};

3. 로직

미네랄의 길이보다, 곡괭이 사용횟수가 적을 수도 있다.
- 이걸 안해주면, 못 캐는 광물까지 5개로 쪼개서 그리디를 해버리게 된다…!
```
int len = (picks[0]+picks[1]+picks[2])*5;
len = (len <= minerals.size()) ? len : minerals.size();
```

5개씩 광물을 쪼갠다.

마지막 쪼가리(?)는 5개보다 적을 수 있다.

for(int i=0; i<len; i+=5) {    
  for(int j=i; j<min(len, i+5); j++) {
    string cur = minerals[j];

탐색
- 크기 3의 배열[다이아몬드, 철, 돌]에 각 피로도 저장
- 각 피로도의 총합을 이용해 pq에 저장
pq에서 하나씩 꺼내면서 다이아몬드 곡괭이부터 소모시킨다.

4. 전체 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

struct Weight
{
    int sum;
    int arr[3];
    
    Weight(int dia, int iron, int stone) {
        sum = dia + iron + stone;
        arr[0] = dia, arr[1] = iron, arr[2] = stone;
    }
    
    bool operator< (const Weight &other) const {
        return sum < other.sum;
    }
};

int solution(vector<int> picks, vector<string> minerals) {
    priority_queue<Weight> pq;
    
    int len = (picks[0]+picks[1]+picks[2])*5;
    len = (len <= minerals.size()) ? len : minerals.size();
    
    for(int i=0; i<len; i+=5) {
        int dia = 0, iron = 0, stone = 0;
        
        for(int j=i; j<min(len, i+5); j++) {
            string cur = minerals[j];
            
            if(cur == "diamond") {
                dia += 1;
                iron += 5;
                stone += 25;
            }
            else if(cur == "iron") {
                dia += 1;
                iron += 1;
                stone += 5;
            }
            else {
                dia += 1;
                iron += 1;
                stone += 1;
            }
        }
        
        pq.push(Weight(dia, iron, stone));
    }
    
    int ans = 0;
    while(!pq.empty()) {
        Weight cur = pq.top();
        pq.pop();
        
        for(int i=0; i<3; i++) {
            if(picks[i] != 0){
                picks[i]--;
                ans += cur.arr[i];
                break;
            }
        }
    }
    
    return ans;
}

5. 소감

문제를 읽자마자 이건 그리디였다.
그러나, 광물을 캐는 순서를 지켜야 하기 때문에 순차 접근으로는 그리디가 불가능했다.
5개씩 쪼개면 순서 안 지켜도 된다는 건.. 어떤 분의 힌트를 보았기 때문이다..
본인은 곡괭이의 피로도를 일일히 입력
- 코드를 보면 14줄에 걸쳐 숫자를 더한다.

unordered_map을 이용해 한줄로 만들 수 있음..

unordered_map<string, int> dic[3] = {
  { { "diamond", 1 }, { "iron", 1 }, { "stone", 1 } },
  { { "diamond", 5 }, { "iron", 1 }, { "stone", 1 } },
  { { "diamond", 25 }, { "iron", 5 }, { "stone", 1 } }
};

Programmers 172927.광물 캐기

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감