Level 2. 광물 캐기

Level 2. 광물 캐기

 

 

우선순위 큐를 활용한 문제인 줄 알았는데, 그냥 완전 탐색 문제였다.

 

최소 비용을 반환하는 DFS 재귀 함수를 만들고, 5개씩 각 곡괭이로 캐보고 가장 적은 비용인 경우를 반환하면 된다.

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int calculate(int pick, size_t from, vector<string>& minerals)
{
    static unordered_map<string, int> cost[3] = {
        {{"diamond", 1},  {"iron", 1}, {"stone", 1}},
        {{"diamond", 5},  {"iron", 1}, {"stone", 1}},
        {{"diamond", 25}, {"iron", 5}, {"stone", 1}}
    };

    int result = 0;

    for (int i = from; i < min(from + 5, minerals.size()); ++i)
        result += cost[pick][minerals[i]];

    return result;
};

int rDFS(int diamond, int iron, int stone, size_t from, vector<string>& minerals)
{
    if (minerals.size() <= from || diamond + iron + stone == 0)
        return 0;

    int result = INT_MAX;

    if (diamond)
        result = min(result, calculate(0, from, minerals) + rDFS(diamond - 1, iron, stone, from + 5, minerals));
    if (iron)
        result = min(result, calculate(1, from, minerals) + rDFS(diamond, iron - 1, stone, from + 5, minerals));
    if (stone)
        result = min(result, calculate(2, from, minerals) + rDFS(diamond, iron, stone - 1, from + 5, minerals));

    return result;
}

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