🖊️ 문제

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

---

🖊️ 풀이

문제가 길다

그래도 일단, 가중치가 있고, 곡괭이로 캘 순서가 어느 정도 정해져있기 때문에 그리디로 푸는 문제라고 생각했다.

근데도 잘 모르겠어서,, 일단 테케를 좀 보려고 DP로 풀어봤다.

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

int arr[3][3] = {{1, 5, 25}, {1, 1, 5}, {1, 1, 1}};
unordered_map<string, int> um;

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    um["diamond"] = 0;
    um["iron"] = 1;
    um["stone"] = 2;
      
    int dp[3] = {0,};
    for (int i = 0 ; i < minerals.size() ; i++) {
        for (int idx = 0 ; idx < 3 ; idx++) {
            if (picks[idx] > 0) {
                dp[idx] += arr[um[minerals[i]]][idx];
            }
        }
        if ((i % 5 == 4 && i != 0) || (i == minerals.size() - 1)) {
            cout << i << " : ";
            int minimum = 987654321;
            for (int i =0 ;i <3 ; i++) {
                cout << dp[i] << " ";
                if (dp[i] != 0) minimum = min(minimum, dp[i]);
            }
            cout << minimum << endl;
            for(int i = 0 ; i < 3 ; i++) {
                if (dp[i] == minimum) {
                    // picks[i]--;
                    answer += dp[i];
                }
               // dp[i] = 0;
            }
        }
    }
        
    return answer;
}

말도 안됨..
이렇게하면 결국 그리디는 쓰지도 못한 풀이였단걸 알 수 있다.

---

그래서 다시.. 천천히 그리디로 생각해봤다.

생각해봐야 할 점

["iron", "iron", "iron", "iron", "iron", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond"]

만약 테스트케이스가 이렇게 주어지면,
["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]
이렇게 주어진 것과 동일하게 써야 한다.

여기서 해결의 실마리가 보였다.

어차피 한 번에 5개씩 끊어서 해결해야 하므로, 광물을 5개씩 끊어놓는다.

위의 경우의 수에서, 마지막 diamond는 캐지 않으므로 고려하지 않는다.
(5개씩 끊은 광물들의 세트 수 > 총 곡괭이의 수 -> 고려X)

그리고, 5개씩 끊어놓은 광물 세트들을 우선순위대로 정렬한 뒤에, 계산하면 된다.

정렬하는 기준은 최악의 경우 기준으로 가중치를 주었다.

다이아 25, 철 5, 돌 1로 가중치를 두었다.

그래서 가중치 기준으로 광물 세트들을 소팅하고, 순서대로 계산하면 된다.

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

bool compare(pair<vector<string>, int>& a, pair<vector<string>, int>& b) {
    return a.second > b.second;
}

int arr[3][3] = {{1, 5, 25}, {1, 1, 5}, {1, 1, 1}};
unordered_map<string, int> um;
unordered_map<string, int> weight;

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    um["diamond"] = 0;
    um["iron"] = 1;
    um["stone"] = 2;
    
    weight["diamond"] = 25;
    weight["iron"] = 5;
    weight["stone"] = 1;
    
    vector<pair<vector<string>, int>> vec;
    
    int total = 0;
    for (int& p : picks) {
        total += p;
    }
    
    vector<string> v;
    int sum = 0;
    for (int i =0 ;i < minerals.size() ; i++) {
        v.push_back(minerals[i]);
        sum += weight[minerals[i]];
        if (i % 5 == 4 || i == minerals.size() - 1) {
            if (vec.size() < total) {
                vec.push_back(make_pair(v,sum));
                v.clear();
                sum = 0;
            }
        }
    }
    
    sort(vec.begin(), vec.end(), compare);
    
    int idx = 0;
    while(picks[idx] <= 0) idx++;
    
    for (auto& v : vec) {
        for (string& s : v.first) {
            answer += arr[um[s]][idx];
        }
        picks[idx]--;
        while(picks[idx] <= 0) idx++;
    }
        
    return answer;
}

1시간 정도 걸렸드..