프로그래머스 172927 광물 캐기

1 개요

프로그래머스 172927 광물 캐기

• 프로그래머스 172927번 문제
• 프로그래머스 Lv. 2.1

2 C++

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

vector<vector<int>> consume = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}};
vector<int> Minerals;
vector<int> Picks;

int dfs(int depth, int count) {
    if (depth >= Minerals.size() || (Picks[0] == 0 && Picks[1] == 0 && Picks[2] == 0)) {
        return count;
    }
    int minCount = 1e9;
    int temp, j;
    for (int i = 0; i < 3; i++) {
        if (Picks[i]) {
            Picks[i]--;
            temp = 0;
            j = depth;
            while (j < depth + 5 && j < Minerals.size()) {
                temp += consume[i][Minerals[j++]];
            }
            minCount = min(minCount, dfs(j, count + temp));
            Picks[i]++;
        }
    }
    return minCount;
}

int solution(vector<int> picks, vector<string> minerals) {
    Minerals.clear();
    Picks = picks;
    for (string& mineral : minerals) {
        if (mineral == "diamond") {
            Minerals.push_back(0);
        } else if (mineral == "iron") {
            Minerals.push_back(1);
        } else {
            Minerals.push_back(2);
        }
    }
    return dfs(0, 0);
}

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

const int fatigue[3][3] = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}};

struct Mineral {
    int diamond;
    int iron;
    int stone;
};

bool compare(const Mineral& a, const Mineral& b) {
    if (a.diamond != b.diamond) return a.diamond > b.diamond;
    if (a.iron != b.iron) return a.iron > b.iron;
    return a.stone > b.stone;
}

int total(const vector<int>& picks) {
    int t = 0;
    for (int pick : picks) {
        t += pick;
    }
    return t;
}

vector<Mineral> collect(const vector<string>& names, int totalMinerals) {
    vector<Mineral> minerals;
    int size = names.size();
    for (int i = 0; i < size && minerals.size() < totalMinerals; i += 5) {
        Mineral m = {0, 0, 0};
        for (int j = i; j < min(i + 5, size); j++) {
            if (names[j] == "diamond") m.diamond++;
            else if (names[j] == "iron") m.iron++;
            else m.stone++;
        }
        minerals.push_back(m);
    }
    return minerals;
}

int score(vector<int> picks, const vector<Mineral>& minerals) {
    int s = 0;
    for (const Mineral& m : minerals) {
        int pickIndex = -1;
        for (int i = 0; i < 3; i++) {
            if (picks[i] > 0) {
                pickIndex = i;
                picks[i]--;
                break;
            }
        }
        if (pickIndex == -1) break;
        s += m.diamond * fatigue[pickIndex][0] +
             m.iron * fatigue[pickIndex][1] +
             m.stone * fatigue[pickIndex][2];
    }
    return s;
}

int solution(vector<int> picks, vector<string> minerals) {
    int totalMinerals = total(picks);
    vector<Mineral> mineralCollection = collect(minerals, totalMinerals);
    sort(mineralCollection.begin(), mineralCollection.end(), compare);
    return score(picks, mineralCollection);
}

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

using namespace std;

struct Tool {
    int diamond, iron, stone;
};

unordered_map<string, Tool> dic = {
    { "diamond", {1, 5, 25} },
    { "iron", {1, 1, 5} },
    { "stone", {1, 1, 1} }
};

int calculateCost(const vector<string>& minerals, int idx, int tool) {
    int cost = 0;
    for (int i = 0; i < 5 && idx + i < minerals.size(); ++i) {
        const Tool& t = dic[minerals[idx + i]];
        cost += (tool == 0 ? t.diamond : (tool == 1 ? t.iron : t.stone));
    }
    return cost;
}

int recursiveMinCost(const vector<int>& picks, const vector<string>& minerals, int a, int b, int c, int idx) {
    if (a + b + c == 0 || idx >= minerals.size()) return 0;
    int ret = 1e9;
    if (a) ret = min(ret, calculateCost(minerals, idx, 0) + recursiveMinCost(picks, minerals, a - 1, b, c, idx + 5));
    if (b) ret = min(ret, calculateCost(minerals, idx, 1) + recursiveMinCost(picks, minerals, a, b - 1, c, idx + 5));
    if (c) ret = min(ret, calculateCost(minerals, idx, 2) + recursiveMinCost(picks, minerals, a, b, c - 1, idx + 5));
    return ret;
}

int solution(vector<int> picks, vector<string> minerals) {
    return recursiveMinCost(picks, minerals, picks[0], picks[1], picks[2], 0);
}