[Programmers] Lv2. 광물 캐기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

저는 백트래킹(Backtracking)을 이용하여 풀었습니다. 구현 과정은 다음과 같습니다.

 

1. 광물을 5개씩 차례대로 분리하고, 남은 광물 수가 5개가 안 될 경우에는 남은 광물을 모조리 담아 2차원 배열 생성
2. 곡괭이 배열과 분리한 2차원 광물 배열을 순회하면서, 곡괭이를 다 썼거나 광물이 없을 때까지 피로도 합산 진행
3. 합산한 피로도가 이전에 계산한 최솟값 피로도보다 작다면 변경
4. 이후 한 단계 뒤로 가서 다음 탐색은 없는지 진행

 

문제를 풀고 나서 다른 분들 풀이는 어떨까 하고 찾아봤는데, 그리디(Greedy)로 푼 사람들도 계시더군요 ㄷㄷ.. 생각을 좀 더 확장해 봐야겠습니다.

 

✏️소스 코드 및 결과

#include <map>
#include <string>
#include <vector>
using namespace std;
const int MAX_CRAFTING = 5;
const int DIAMOND_PICK_IDX = 0;
const int IRON_PICK_IDX = 1;
const int STONE_PICK_IDX = 2;


map<pair<int, string>, int> stressFatigues {
    {make_pair(DIAMOND_PICK_IDX, "diamond"), 1},    // 다이아 곡괭이, 다이아 광물
    {make_pair(DIAMOND_PICK_IDX, "iron"),    1},    // 다이아 곡괭이, 철 광물
    {make_pair(DIAMOND_PICK_IDX, "stone"),   1},    // 다이아 곡괭이, 돌 광물

    {make_pair(IRON_PICK_IDX, "diamond"),    5},    // 철 곡괭이, 다이아 광물
    {make_pair(IRON_PICK_IDX, "iron"),       1},    // 철 곡괭이, 철 광물
    {make_pair(IRON_PICK_IDX, "stone"),      1},    // 철 곡괭이, 돌 광물

    {make_pair(STONE_PICK_IDX, "diamond"),  25},    // 돌 곡괭이, 다이아 광물
    {make_pair(STONE_PICK_IDX, "iron"),      5},    // 돌 곡괭이, 철 광물
    {make_pair(STONE_PICK_IDX, "stone"),     1},    // 돌 곡괭이, 돌 광물
};

int CalculteStressFatigue(const int currentPick, const vector<string>& selectedMinerals) {
    int result = 0;

    for (int i = 0; i < selectedMinerals.size(); i++)
        result += stressFatigues[make_pair(currentPick, selectedMinerals[i])];
    return result;
}


void SearchMinStressFatigue(vector<int>& picks, const vector<vector<string>>& splitMinerals, int currentIdx, int& sum, int& minValue) {
    bool isCompleteMining = true;
    
    for (int i = 0; i < picks.size(); i++) {
        if (picks[i] > 0 and currentIdx < splitMinerals.size()) {
            isCompleteMining = false;
            int totalStressFatigue = CalculteStressFatigue(i, splitMinerals[currentIdx]);
            picks[i]--;
            sum += totalStressFatigue;

            SearchMinStressFatigue(picks, splitMinerals, currentIdx + 1, sum, minValue);

            sum -= totalStressFatigue;
            picks[i]++;
        }
    }

    if (isCompleteMining) {
        if (sum < minValue)
            minValue = sum;
    }
}

int FindMinStressFatigue(const vector<vector<string>>& splitMinerals, vector<int>& picks) {
    int sum = 0;
    int minValue = 2147483647;
    SearchMinStressFatigue(picks, splitMinerals, 0, sum, minValue);
    
    return minValue;
}


vector<vector<string>> SplitMinerals(const vector<string>& originalMinerals) {
    vector<vector<string>> result;

    for (int i = 0; i < originalMinerals.size(); i += MAX_CRAFTING) {
        vector<string> minerals;

        for (int j = i; j < originalMinerals.size() and j < i + MAX_CRAFTING; j++)
            minerals.push_back(originalMinerals[j]);

        result.push_back(minerals);
    }

    return result;
}


int solution(vector<int> picks, vector<string> minerals) {
    vector<vector<string>> splitedMinerals = SplitMinerals(minerals);
    int answer = FindMinStressFatigue(splitedMinerals, picks);
    return answer;
}

제출 결과